The range search in Hamming space is to explore the binary vectors whose Hamming distances with a query vector are within a given searching threshold. It arises as the core component of many applications, such as image retrieval, pattern recognition, and machine learning. Existing searching methods in Hamming space require much pre-processing overhead, which are not suitable for processing multiple batches of incoming data in a short time. Moreover, significant pre-processing overhead can be a burden when the number of queries is relatively small. In this paper, we propose a query-aware method for the approximate range search in Hamming space with no pre-process. Specifically, to eliminate the impact of data skewness, we introduce JS-divergence to measure the divergence between data's distribution and query's distribution, and specially design a Query-Aware Dimension Partitioning (QADP) strategy to partition the dimensions into several subspaces according to the scales of given searching thresholds. In the subspaces, the candidates can be efficiently obtained by the basic Pigeonhole Principle and our proposed Anti-Pigeonhole Principle. Furthermore, a sampling strategy is designed to estimate the Hamming distance between the query vector and arbitrary binary vector to obtain the final approximate searching results among the candidates. Experimental results on four real-world datasets illustrate that, in comparison with benchmark methods, our method possesses the superior advantages on searching accuracy and efficiency. The proposed method can increase the searching efficiency up to nearly 16 times with high searching accuracy.

With the development of intelligent logistics technology, some companies began to use robots instead of humans to load cargo. This paper studies a novel container loading problem based on robotic loader system (CLP-RLS). Different from the existing robot-packable pattern in the literature, the robotic loader system in this paper consists of a depalletizing robot, an automatic telescopic roller line and a loading robot, in which the loading robot will enter the carriage along with the automatic telescopic roller line. In CLP-RLS, it is necessary to consider not only many practical constraints already in the literature, including load balancing, orientation, stability, and multi-drop but also two new constraints related to robotic loader system: pallet continuity constraint (the loading sequence of cargo on the same pallet is continuous) and robot position constraint (the robot can only load cargo incrementally from the front to the back of the truck). Due to the difficulty in modeling CLP-RLS and the large scale of the real-case instances, we present a tree search approach based on wall-building to solve CLP-RLS, intending to find a feasible loading scheme for the RLS to minimize the length required to load all cargo. The effectiveness of the proposed approach is verified through both real-case instances and numerical instances.

The current global economy is undergoing a transformative phase, emphasizing collaboration among multiple competing entities rather than monopolization. Economic globalization is accelerating the adoption of globalized cloud services, and in line with this trend, cloud 2.0 introduces the concept of “cloud cooperation”. JointCloud, as a novel computing model for Cloud 2.0, advocates for the establishment of an evolving cloud ecosystem. However, a critical challenge arises due to the lack of direct incentives for a cloud to join the JointCloud ecosystem, leading to uncertainty regarding the rationale for the existence of the JointCloud ecosystem. To address this ambiguity, we draw inspiration from supply chain competition and formulate the market dynamics of resources within the JointCloud ecosystem. Our focus is particularly on the analysis of data resource trade within the JointCloud market. To comprehensively analyze the JointCloud market, we propose a market game that examines the competition among clouds within the ecosystem. We theoretically prove that a Nash Equilibrium always exists under the JointCloud market. Subsequently, we conduct an in-depth analysis of the profits of cloud resource manufacturers and cloud resource retailers as the number of clouds varies within the JointCloud ecosystem. Based on our analysis, we further explore the incentives for a cloud to participate in the JointCloud ecosystem. We then evaluate the performance of the proposed market game through extensive experiments, illustrating how process variables and profits change with the market size. The experiments demonstrate that the trends of various variables are aligned with our analysis obtained from the market game. Compared with the Cournot model, our proposed model captures the market power of both manufacturers and retailers, resulting in a model that closely mirrors real market dynamics. Our findings provide valuable insights into the cloud market within Cloud 2.0, offering guidance for stakeholders navigating the evolving landscape of cloud cooperation and competition.

Bregman distances (also known as Bregman divergences) are widely used in machine learning, speech recognition and signal processing, and kNN searches with Bregman distances have become increasingly important with the rapid advances of multimedia applications. Data in multimedia applications such as images and videos are commonly transformed into space of hundreds of dimensions. Such high-dimensional space has posed significant challenges for existing kNN search algorithms with Bregman distances, which could only handle data of medium dimensionality (typically less than 100). This paper addresses the urgent problem of high-dimensional kNN search with Bregman distances. We propose a novel partition-filter-refinement framework. Specifically, we propose an optimized dimensionality partitioning scheme to solve several non-trivial issues. First, an effective bound from each partitioned subspace to obtain exact kNN results is derived. Second, we conduct an in-depth analysis of the optimized number of partitions and devise an effective strategy for partitioning. Third, we design an efficient integrated index structure for all the subspaces together to accelerate the search processing. Moreover, we extend our exact solution to an approximate version by a trade-off between the accuracy and efficiency. Experimental results on four real-world datasets and two synthetic datasets show the clear advantage of our method in comparison to state-of-the-art algorithms.

Bregman distances (also known as Bregman divergences) are widely used in machine learning, speech recognition and signal processing, andkNN searches with Bregman distances have become increasingly important with the rapid advances of multimedia applications. Data in multimedia applications such as images and videos are commonly transformed into space of hundreds of dimensions. Such high-dimensional space has posed significant challenges for existingkNN search algorithms with Bregman distances, which could only handle data of medium dimensionality (typically less than 100). This paper addresses the urgent problem of high-dimensionalkNN search with Bregman distances. We propose a novel partition-filter-refinement framework. Specifically, we propose an optimized dimensionality partitioning scheme to solve several non-trivial issues. First, an effective bound from each partitioned subspace to obtain exactkNN results is derived. Second, we conduct an in-depth analysis of the optimized number of partitions and devise an effective strategy for partitioning. Third, we design an efficient integrated index structure for all the subspaces together to accelerate the search processing. Moreover, we extend our exact solution to an approximate version by a trade-off between the accuracy and efficiency. Experimental results on four real-world datasets and two synthetic datasets show the clear advantage of our method in comparison to state-of-the-art algorithms.

Due to the wide applications in recommendation systems, multi-class label prediction and deep learning, the Maximum Inner Product (MIP) search problem has received extensive attention in recent years. Faced with large-scale datasets containing high-dimensional feature vectors, the state-of-the-art LSH-based methods usually require a large number of hash tables or long hash codes to ensure the searching quality, which takes up lots of index space and causes excessive disk page accesses. In this paper, we relax the guarantee of accuracy for efficiency and propose an efficient method for c-Approximate Maximum Inner Product (c-AMIP) search with a lightweight iDistance index. We project high-dimensional points to low-dimensional ones via 2-stable random projections and derive probability-guaranteed searching conditions, by which the c-AMIP results can be guaranteed in accuracy with arbitrary probabilities. To further improve the efficiency, we propose Quick-Probe for quickly determining the searching bound satisfying the derived condition in advance, avoiding the inefficient incremental searching process. Extensive experimental evaluations on four real datasets demonstrate that our method requires less pre-processing cost including index size and pre-processing time. In addition, compared to the state-of-the-art benchmark methods, it provides superior results on searching quality in terms of overall ratio and recall, and efficiency in terms of page access and running time.

The k Nearest Neighbor (k-NN) query has been gaining more importance in extensive applications involving information retrieval, data mining, and databases. Specifically, in order to trade off accuracy for efficiency, approximate solutions for the k-NN query are extensively explored. However, the precision is usually order-insensitive, which is defined on the result set instead of the result sequence. In many situations, it cannot reasonably reflect the query result quality. In this paper, we focus on the approximate k-NN query problem with the order-sensitive precision requirement and propose a novel scheme based on the projection-filter-refinement framework. Basically, we adopt PCA to project the high-dimensional data objects into the low-dimensional space. Then, a filter condition is inferred to execute efficient pruning over the projected data. In addition, an index strategy named OR-tree is proposed to reduce the I/O cost. The extensive experiments based on several real-world data sets and a synthetic data set are conducted to verify the effectiveness and efficiency of the proposed solution. Compared to the state-of-the-art methods, our method can support order-sensitive k -NN queries with higher result precision while retaining satisfactory CPU and I/O efficiency.