OpenRaiser/Intern-Atlas huggingface dataset:
Enhancing Dynamic On-demand Food Order Dispatching via Future-informed and Spatial-temporal Extended Decisions
Authors: Yile Liang, Donghui Li, Jiuxia Zhao, Xuetao Ding, Huanjia Lian, Jinghua Hao, Renqing He
Venue: Conference CIKM 2023
Year: 2023

On-demand food delivery (OFD) service has gained fast-growing popularity all around the world. Order dispatching is instrumental to large-scale OFD platforms, such as Meituan, which continuously match food order requests to couriers at a scale of tens of millions each day to satisfy the needs of consumers, couriers, and merchants. However, due to high dynamism and inevitable uncertainties in the real-world environment, it is not an easy task to achieve long-term global objective optimization through continuous isolated optimization decisions at each dispatch moment. Our work proposes the concept of "courier occupancy" (CO) to precisely quantify the impact of order assignment on the courier's delivery efficiency, realizing a decomposition of long-term and macro goals into various dispatch moments and micro decision-making dimensions. Then in the prediction phase, an improved and universally applicable distribution estimation method is designed to quantify CO which is a stochastic variable and contains future information, combining Monte Carlo dropout and knowledge distillation. In the optimization phase, we use CO to model the objective function at each dispatch moment to introduce future information and extend dispatch decisions from merely who to assign the order to both when and who to assign it, significantly enhancing the long-term optimization capability of dispatching decisions and avoiding local greed. We conduct extensive offline simulations based on real dispatching data as well as online AB tests through Meituan's platform. Results show that our method consistently improves the couriers' delivery efficiency and consumers' satisfaction.
HyperLogLogLog: Cardinality Estimation With One Log More
Authors: Matti Karppa, Rasmus Pagh
Venue: Conference KDD 2022
Year: 2022

We present HyperLogLogLog, a practical compression of the HyperLogLog sketch that compresses the sketch from $O(m\log\log n)$ bits down to $m \log_2\log_2\log_2 m + O(m+\log\log n)$ bits for estimating the number of distinct elements~$n$ using $m$~registers. The algorithm works as a drop-in replacement that preserves all estimation properties of the HyperLogLog sketch, it is possible to convert back and forth between the compressed and uncompressed representations, and the compressed sketch maintains mergeability in the compressed domain. The compressed sketch can be updated in amortized constant time, assuming $n$ is sufficiently larger than $m$. We provide a C++ implementation of the sketch, and show by experimental evaluation against well-known implementations by Google and Apache that our implementation provides small sketches while maintaining competitive update and merge times. Concretely, we observed approximately a 40% reduction in the sketch size. Furthermore, we obtain as a corollary a theoretical algorithm that compresses the sketch down to $m\log_2\log_2\log_2\log_2 m+O(m\log\log\log m/\log\log m+\log\log n)$ bits.
Towards optimal cardinality estimation of unions and intersections with sketches
Authors: Daniel Ting
Venue: Conference KDD 2016
Year: 2016

Estimating the cardinality of unions and intersections of sets is a problem of interest in OLAP. Large data applications often require the use of approximate methods based on small sketches of the data. We give new estimators for the cardinality of unions and intersection and show they approximate an optimal estimation procedure. These estimators enable the improved accuracy of the streaming MinCount sketch to be exploited in distributed settings. Both theoretical and empirical results demonstrate substantial improvements over existing methods.
Discrete conditional diffusion for reranking in recommendation
Authors: Xiao Lin, Xiaokai Chen, Chenyang Wang, Hantao Shu, Linfeng Song, Biao Li, Peng Jiang
Venue: Conference WWW 2024
Year: 2024

Reranking plays a crucial role in modern multi-stage recommender systems by rearranging the initial ranking list to model interplay between items. Considering the inherent challenges of reranking such as combinatorial searching space, some previous studies have adopted the evaluator-generator paradigm, with a generator producing feasible sequences and a evaluator selecting the best one based on estimated listwise utility. This paper explores the potential of diffusion models for generating high-quality sequences in reranking tasks, as the intrinsic nature of diffusion models is to improve generation quality by iterative refinements of generated samples. However, we argue that it is nontrivial to take diffusion models as the generator in the context of recommendation. Firstly, diffusion models primarily operate in continuous data space, differing from the discrete data space of item permutations. Secondly, the recommendation task is different from conventional generation tasks as the purpose of recommender systems is to fulfill user interests. Lastly, real-life recommender systems require efficiency, posing challenges for the inference of diffusion models. To overcome these challenges, we propose a novel Discrete Conditional Diffusion Reranking (DCDR) framework for recommendation. DCDR extends traditional diffusion models by introducing a discrete forward process with tractable posteriors, which adds noise to item sequences through step-wise discrete operations (e.g., swapping). Additionally, DCDR incorporates a conditional reverse process that generates item sequences conditioned on expected user responses. For efficient and robust inference, we propose several optimizations to enable the deployment of DCDR in real-life recommender systems. Extensive offline experiments conducted on public datasets demonstrate that DCDR outperforms state-of-the-art reranking methods. Furthermore, DCDR has been deployed in a real-world video app with over 300 million daily active users, significantly enhancing online recommendation quality.
Short and Long-Term Pattern Discovery Over Large-Scale Geo-Spatiotemporal Data
Authors: Sobhan Moosavi, Mohammad Hossein Samavatian, Arnab Nandi, Srinivasan Parthasarathy, Rajiv Ramnath
Venue: Conference KDD 2019
Year: 2019

Pattern discovery in geo-spatiotemporal data (such as traffic and weather data) is about finding patterns of collocation, co-occurrence, cascading, or cause and effect between geospatial entities. Using simplistic definitions of spatiotemporal neighborhood (a common characteristic of the existing general-purpose frameworks) is not semantically representative of geo-spatiotemporal data. We therefore introduce a new geo-spatiotemporal pattern discovery framework which defines a semantically correct definition of neighborhood; and then provides two capabilities, one to explore propagation patterns and the other to explore influential patterns. Propagation patterns reveal common cascading forms of geospatial entities in a region. Influential patterns demonstrate the impact of temporally long-term geospatial entities on their neighborhood. We apply this framework on a large dataset of traffic and weather data at countrywide scale, collected for the contiguous United States over two years. Our important findings include the identification of 90 common propagation patterns of traffic and weather entities (e.g., rain --> accident --> congestion), which results in identification of four categories of states within the US; and interesting influential patterns with respect to the "location", "duration", and "type" of long-term entities (e.g., a major construction --> more traffic incidents). These patterns and the categorization of the states provide useful insights on the driving habits and infrastructure characteristics of different regions in the US, and could be of significant value for applications such as urban planning and personalized insurance.
ST-MoE: Spatio-Temporal Mixture-of-Experts for Debiasing in Traffic Prediction
Authors: Shuhao Li, Yue Cui, Yan Zhao, Weidong Yang, Ruiyuan Zhang, Xiaofang Zhou
Venue: Conference CIKM 2023
Year: 2023

The pervasiveness of GPS-enabled devices and wireless communication technologies results in a proliferation of traffic data in intelligent transportation systems, where traffic prediction is often essential to enable reliability and safety. Many recent studies target traffic prediction using deep learning techniques. They model spatio-temporal dependencies among traffic states by deep learning and achieve good overall performance. However, existing studies ignore the bias on traffic prediction models, which refers to non-uniformed performance distribution across road segments, especially the significantly poor prediction results on certain road segments. To solve this issue, we propose a framework named spatio-temporal mixture-of-experts (ST-MoE) that aims to eliminate the bias on traffic prediction. In general, we refer to any traffic prediction model as the based model, and adopt the proposed ST-MoE framework as a plug-in to debias. ST-MoE uses stacked convolution-based networks to learn spatio-temporal representations of individual patterns of road segments and then adaptively assigns appropriate expert layers (sub-networks) to different patterns through a spatio-temporal gating network. To this end, the patterns can be distinguished, and biased performance among road segments can be eliminated by experts tailored for specific patterns, which also further improves the overall prediction accuracy of the base model. Extensive experimental results on various base models and real-world datasets prove the effectiveness of ST-MoE.
DuTraffic: Live Traffic Condition Prediction with Trajectory Data and Street Views at Baidu Maps
Authors: Deguo Xia, Xiyan Liu, Wei Zhang, Hui Zhao, Chengzhou Li, Weiming Zhang, Jizhou Huang, Haifeng Wang
Venue: Conference CIKM 2022
Year: 2022

The task of live traffic condition prediction, which aims at predicting live traffic conditions (i.e., fast, slow, and congested) based on traffic information on roads, plays a vital role in intelligent transportation systems, such as navigation, route planning, and ride-hailing services. Existing solutions have adopted aggregated trajectory data to generate traffic estimates, which inevitably suffer from GPS drift caused by cluttered urban road scenarios. In addition, the trajectory information alone is insufficient to provide evidence for sudden traffic situations and perception of street-wise elements. To alleviate these problems, in this paper, we present DuTraffic, which is a robust and production-ready solution for live traffic condition prediction by taking both trajectory data and street views into account. Specifically, the vision-based detection and segmentation modules are developed to forecast traffic flow by using street views. Then, we propose a spatial-temporal-based module, TRST-Net, to learn the latent trajectory representation. Finally, a bilinear model is introduced to mix these two representations and then predicts live traffic conditions with trajectory data and street views in a mutually complementary manner. The task is recast as a multi-task learning problem, which could benefit from the strong representation of latent space manifold modeling. Extensive experiments conducted on large-scale, real-world datasets from Baidu Maps demonstrate the superiority and effectiveness of DuTraffic. In addition, DuTraffic has already been deployed in production at Baidu Maps since December 2020, handling tens of millions of requests every day. This demonstrates that DuTraffic is a practical and robust industrial solution for live traffic condition prediction.
DuETA: Traffic congestion propagation pattern modeling via efficient graph learning for ETA prediction at Baidu Maps
Authors: Jizhou Huang, Zhengjie Huang, Xiaomin Fang, Shikun Feng, Xuyi Chen, Jiaxiang Liu, Haitao Yuan, Haifeng Wang
Venue: Conference CIKM 2022
Year: 2022

Estimated time of arrival (ETA) prediction, also known as travel time estimation, is a fundamental task for a wide range of intelligent transportation applications, such as navigation, route planning, and ride-hailing services. To accurately predict the travel time of a route, it is essential to take into account both contextual and predictive factors, such as spatial-temporal interaction, driving behavior, and traffic congestion propagation inference. The ETA prediction models previously deployed at Baidu Maps have addressed the factors of spatial-temporal interaction (ConSTGAT) and driving behavior (SSML). In this work, we believe that modeling traffic congestion propagation patterns is of great importance toward accurately performing ETA prediction, and we focus on this factor to improve ETA performance. Traffic congestion propagation pattern modeling is challenging, and it requires accounting for impact regions over time and cumulative effect of delay variations over time caused by traffic events on the road network. In this paper, we present a practical industrial-grade ETA prediction framework named DuETA. Specifically, we construct a congestion-sensitive graph based on the correlations of traffic patterns, and we develop a route-aware graph transformer to directly learn the long-distance correlations of the road segments. This design enables DuETA to capture the interactions between the road segment pairs that are spatially distant but highly correlated with traffic conditions. Extensive experiments are conducted on large-scale, real-world datasets collected from Baidu Maps. Experimental results show that ETA prediction can significantly benefit from the learned traffic congestion propagation patterns, which demonstrates the effectiveness and practical applicability of DuETA. In addition, DuETA has already been deployed in production at Baidu Maps, serving billions of requests every day. This demonstrates that DuETA is an industrial-grade and robust solution for large-scale ETA prediction services.
DuARUS: Automatic Geo-object Change Detection with Street View Imagery for Updating Road Database at Baidu Maps
Authors: Deguo Xia, Jizhou Huang, Jianzhong Yang, Xiyan Liu, Haifeng Wang
Venue: Conference CIKM 2022
Year: 2022

As the core foundation of web mapping, each geographic object (geo-object), such as a traffic sign, plays a vital role in navigation and intelligent driving. Determining how to obtain the latest high-precision geo-object information is a classic topic in updating road databases. Benefiting from the cost-effective attribute and availability of the positioning equipment and camera, the vision-based update pattern is becoming increasingly popular in the industry. Generally speaking, the road database update mainly includes three phases: geo-object recognition, localization, and change detection. Previous change detection strategies are mainly performed by comparing the historical road information (i.e., geo-object type and position) with the new geographic data of geo-objects collected from the street-view imagery. However, limited by the localization precision of the positioning equipment and the discriminative power of the vanilla differential-based method, the accuracy, recall, and efficiency of previous systems for geo-object change detection are greatly impaired. In addition, the artificially prescribed production standards make the geo-object position in the map data deviate from its position in the real world, as well as some geo-objects do not need to be updated (e.g., temporary speed limit), which further yields many false-positive detections and significantly increases the labor costs of existing systems. To address these challenges, we propose a novel framework called DuARUS for automatic geo-object change detection with street-view imagery. In this paper, we mainly focus on automatic geo-object localization and change detection. Specifically, for geo-object localization, we propose a two-stage, integrated localization algorithm based on image matching and monocular depth estimation. Furthermore, to achieve automatic change detection, vision-based representation learning and scene understanding strategies are introduced to build a large-scale geo-object semantic map, which can provide sufficient multimodal information support for change detection. Based on such artful modeling, we recast the complicated, labor-based change detection problem as a vanilla binary classification task, which is a robust and efficient strategy that contributes to resolving this problem. By combining these operations, we construct an industrial-grade, fully automatic production system for road database updates. Extensive experiments conducted on large-scale, real-world datasets from Baidu Maps demonstrate the superiority and effectiveness of the system. Moreover, this system has already been deployed in production at Baidu Maps since July 2020, handling 96% of automatic road database updates. DuARUS improves the annual update mileage from millions to tens of millions, and it achieves weekly updates.
Combining multiple evidence from different types of thesaurus for query expansion
Authors: Rila Mandala, Takenobu Tokunaga, Hozumi Tanaka
Venue: Conference SIGIR 1999
Year: 1999

Automatic query expansion has been known to be the most important method in overcoming the word mismatch problem in information retrieval. Thesauri have long been used by many researchers as a tool for query expansion. However only one type of thesaurus has generally been used. In this paper we analyze the characteristics of different thesaurus types and propose a method to combine them for query expansion. Experiments using the TREC collection proved the effectiveness of our method over those using one type of thesaurus.
How dataset characteristics affect the robustness of collaborative recommendation models
Authors: Yashar Deldjoo, Tommaso Di Noia, Eugenio Di Sciascio, Felice Antonio Merra
Venue: Conference SIGIR 2020
Year: 2020

Shilling attacks against collaborative filtering (CF) models are characterized by several fake user profiles mounted on the system by an adversarial party to harvest recommendation outcomes toward a malicious desire. The vulnerability of CF models is directly tied with their reliance on the underlying interaction data ---like user-item rating matrix (URM) --- to train their models and their inherent inability to distinguish genuine profiles from non-genuine ones. The majority of works conducted so far for analyzing shilling attacks mainly focused on properties such as confronted recommendation models, recommendation outputs, and even users under attack. The under-researched element has been the impact of data characteristics on the effectiveness of shilling attacks on CF models.
Popularity-aware alignment and contrast for mitigating popularity bias
Authors: Miaomiao Cai 0001, Lei Chen 0051, Yifan Wang 0017, Haoyue Bai 0002, Peijie Sun, Le Wu, Min Zhang 0006, Meng Wang 0001
Venue: Conference KDD 2024
Year: 2024

Collaborative Filtering~(CF) typically suffers from the significant challenge of popularity bias due to the uneven distribution of items in real-world datasets. This bias leads to a significant accuracy gap between popular and unpopular items. It not only hinders accurate user preference understanding but also exacerbates the Matthew effect in recommendation systems. To alleviate popularity bias, existing efforts focus on emphasizing unpopular items or separating the correlation between item representations and their popularity. Despite the effectiveness, existing works still face two persistent challenges: (1) how to extract common supervision signals from popular items to improve the unpopular item representations, and (2) how to alleviate the representation separation caused by popularity bias. In this work, we conduct an empirical analysis of popularity bias and propose <u>P</u>opularity-<u>A</u>ware <u>A</u>lignment and <u>C</u>ontrast (PAAC) to address two challenges. Specifically, we use the common supervisory signals modeled in popular item representations and propose a novel popularity-aware supervised alignment module to learn unpopular item representations. Additionally, we suggest re-weighting the contrastive learning loss to mitigate the representation separation from a popularity-centric perspective. Finally, we validate the effectiveness and rationale of PAAC in mitigating popularity bias through extensive experiments on three real-world datasets. Our code is available at https://github.com/miaomiao-cai2/KDD2024-PAAC.
Multi-view multi-aspect neural networks for next-basket recommendation
Authors: Zhiying Deng, Jianjun Li, Zhiqiang Guo, Wei Liu, Li Zou, Guohui Li
Venue: Conference SIGIR 2023
Year: 2023

Next-basket recommendation (NBR) is a type of recommendation that aims to recommend a set of items to users according to their historical basket sequences. Existing NBR methods suffer from two limitations: (1) overlooking low-level item correlations, which results in coarse-grained item representation; and (2) failing to consider spurious interests in repeated behaviors, leading to suboptimal user interest learning. To address these limitations, we propose a novel solution named Multi-view Multi-aspect Neural Recommendation (MMNR) for NBR, which first normalizes the interactions from both the user-side and item-side, respectively, aiming to remove the spurious interests, and utilizes them as weights for items from different views to construct differentiated representations for each interaction item, enabling comprehensive user interest learning. Then, to capture low-level item correlations, MMNR models different aspects of items to obtain disentangled representations of items, thereby fully capturing multiple user interests. Extensive experiments on real-world datasets demonstrate the effectiveness of MMNR, showing that it consistently outperforms several state-of-the-art NBR methods.
Parallel knowledge enhancement based framework for multi-behavior recommendation
Authors: Chang Meng, Chenhao Zhai, Yu Yang, Hengyu Zhang, Xiu Li
Venue: Conference CIKM 2023
Year: 2023

Multi-behavior recommendation algorithms aim to leverage the multiplex interactions between users and items to learn users' latent preferences. Recent multi-behavior recommendation frameworks contain two steps: fusion and prediction. In the fusion step, advanced neural networks are used to model the hierarchical correlations between user behaviors. In the prediction step, multiple signals are utilized to jointly optimize the model with a multi-task learning (MTL) paradigm. However, recent approaches have not addressed the issue caused by imbalanced data distribution in the fusion step, resulting in the learned relationships being dominated by high-frequency behaviors. In the prediction step, the existing methods use a gate mechanism to directly aggregate expert information generated by coupling input, leading to negative information transfer. To tackle these issues, we propose a Parallel Knowledge Enhancement Framework (PKEF) for multi-behavior recommendation. Specifically, we enhance the hierarchical information propagation in the fusion step using parallel knowledge (PKF). Meanwhile, in the prediction step, we decouple the representations to generate expert information and introduce a projection mechanism during aggregation to eliminate gradient conflicts and alleviate negative transfer (PME). We conduct comprehensive experiments on three real-world datasets to validate the effectiveness of our model. The results further demonstrate the rationality and effectiveness of the designed PKF and PME modules. The source code and datasets are available at https://github.com/MC-CV/PKEF.