Search

A moving $k$ NN query continuously reports the $k$ results (restaurants) nearest to a moving query point (tourist). In addition to the query results, a service provider often returns to a mobile client a safe region that bounds the validity of query results in order to minimize the communication cost between the service provider and that mobile client. However, when a service provider is not trustworthy, it may send inaccurate query results or incorrect safe regions to mobile clients. In this paper, we present a framework for authenticating both the query results and the safe regions of moving $k$ NN queries. We theoretically proved that our methods for authenticating moving $k$ NN queries minimize the data sent between the service provider and the mobile clients. Extensive experiments are carried out using both real and synthetic data sets and results show that our methods can perform moving $k$ NN query authentication with small communication costs and overhead. [ABSTRACT FROM PUBLISHER]

A graph is called hidden if the edges are not explicitly given and edge probe tests are required to detect the presence of edges. This paper studies the $(k)$ most connected vertices ($(k)$MCV) problem on hidden bipartite graphs, which has applications in spatial databases, graph databases, and bioinformatics. There is a prior work on the $(k)$MCV problem, which is based on the "2-vertex testing" model, i.e., an edge probe test can only reveal the existence of an edge between two individual vertices. We study the $(k)$MCV problem, in the context of a more general edge probe test model called "group testing." A group test can reveal whether there exists some edge between a vertex and a group of vertices. If group testing is used properly, a single invocation of a group test can reveal as much information as multiple invocations of 2-vertex tests. We discuss the cases and applications where group testing could be used, and present an algorithm, namely, GMCV, that adaptively leverages group testing to solve the $(k)$MCV problem. [ABSTRACT FROM AUTHOR]

Data cube is a key element in supporting fast OLAP. Traditionally, an aggregate function is used to compute the values in data cubes. In this paper, we extend the notion of data cubes with a new perspective. Instead of using an aggregate function, we propose to build data cubes using the skyline operation as the “aggregate function.” Data cubes built in this way are called “group-by skyline cubes” and can support a variety of analytical tasks. Nevertheless, there are several challenges in implementing group-by skyline cubes in data warehouses: 1) the skyline operation is computational intensive, 2) the skyline operation is holistic, and 3) a group-by skyline cube contains both grouping and skyline dimensions, rendering it infeasible to precompute all cuboids in advance. This paper gives details on how to store, materialize, and query such cubes. [ABSTRACT FROM AUTHOR]