Open Access. Powered by Scholars. Published by Universities.®
Databases and Information Systems Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Road Network Databases (4)
- Spatial Optimization (3)
- Spatial databases (3)
- Air indexes (2)
- Location-based services (2)
-
- Query processing (2)
- Real road networks (2)
- Transportation network (2)
- Wireless broadcast (2)
- Access latency (1)
- Approximate algorithms (1)
- Approximation theory (1)
- Broadcast channels (1)
- Cardinalities (1)
- Computational capability (1)
- Continuous Query Monitoring (1)
- Continuous monitoring (1)
- Cost values (1)
- Data structures (1)
- Device specification (1)
- Direct neighbors (1)
- Energy consumption (1)
- Euclidean (1)
- Exact algorithms (1)
- Heuristic techniques (1)
- Indexing framework (1)
- Location Privacy (1)
- Location dependents (1)
- Location privacy (1)
- Low-dimensional search (1)
Articles 1 - 10 of 10
Full-Text Articles in Databases and Information Systems
Direct Neighbor Search, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang
Direct Neighbor Search, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang
Kyriakos MOURATIDIS
In this paper we study a novel query type, called direct neighbor query. Two objects in a dataset are direct neighbors (DNs) if a window selection may exclusively retrieve these two objects. Given a source object, a DN search computes all of its direct neighbors in the dataset. The DNs define a new type of affinity that differs from existing formulations (e.g., nearest neighbors, nearest surrounders, reverse nearest neighbors, etc.) and finds application in domains where user interests are expressed in the form of windows, i.e., multi-attribute range selections. Drawing on key properties of the DN relationship, we develop an …
Heuristic Algorithms For Balanced Multi-Way Number Partitioning, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang
Heuristic Algorithms For Balanced Multi-Way Number Partitioning, Jilian Zhang, Kyriakos Mouratidis, Hwee Hwa Pang
Kyriakos MOURATIDIS
Balanced multi-way number partitioning (BMNP) seeks to split a collection of numbers into subsets with (roughly) the same cardinality and subset sum. The problem is NP-hard, and there are several exact and approximate algorithms for it. However, existing exact algorithms solve only the simpler, balanced two-way number partitioning variant, whereas the most effective approximate algorithm, BLDM, may produce widely varying subset sums. In this paper, we introduce the LRM algorithm that lowers the expected spread in subset sums to one third that of BLDM for uniformly distributed numbers and odd subset cardinalities. We also propose Meld, a novel strategy for …
Tree-Based Partition Querying: A Methodology For Computing Medoids In Large Spatial Datasets, Kyriakos Mouratidis, Dimitris Papadias, Spiros Papadimitriou
Tree-Based Partition Querying: A Methodology For Computing Medoids In Large Spatial Datasets, Kyriakos Mouratidis, Dimitris Papadias, Spiros Papadimitriou
Kyriakos MOURATIDIS
Besides traditional domains (e.g., resource allocation, data mining applications), algorithms for medoid computation and related problems will play an important role in numerous emerging fields, such as location based services and sensor networks. Since the k-medoid problem is NP hard, all existing work deals with approximate solutions on relatively small datasets. This paper aims at efficient methods for very large spatial databases, motivated by: (i) the high and ever increasing availability of spatial data, and (ii) the need for novel query types and improved services. The proposed solutions exploit the intrinsic grouping properties of a data partition index in order …
Anonymous Query Processing In Road Networks, Kyriakos Mouratidis, Man Lung Yiu
Anonymous Query Processing In Road Networks, Kyriakos Mouratidis, Man Lung Yiu
Kyriakos MOURATIDIS
The increasing availability of location-aware mobile devices has given rise to a flurry of location-based services (LBSs). Due to the nature of spatial queries, an LBS needs the user position in order to process her requests. On the other hand, revealing exact user locations to a (potentially untrusted) LBS may pinpoint their identities and breach their privacy. To address this issue, spatial anonymity techniques obfuscate user locations, forwarding to the LBS a sufficiently large region instead. Existing methods explicitly target processing in the euclidean space and do not apply when proximity to the users is defined according to network distance …
On-Line Discovery Of Hot Motion Paths, Dimitris Sacharidis, Kostas Patroumpas, Manolis Terrovitis, Verena Kantere, Michalis Potamias, Kyriakos Mouratidis, Timos Sellis
On-Line Discovery Of Hot Motion Paths, Dimitris Sacharidis, Kostas Patroumpas, Manolis Terrovitis, Verena Kantere, Michalis Potamias, Kyriakos Mouratidis, Timos Sellis
Kyriakos MOURATIDIS
We consider an environment of numerous moving objects, equipped with location-sensing devices and capable of communicating with a central coordinator. In this setting, we investigate the problem of maintaining hot motion paths, i.e., routes frequently followed by multiple objects over the recent past. Motion paths approximate portions of objects' movement within a tolerance margin that depends on the uncertainty inherent in positional measurements. Discovery of hot motion paths is important to applications requiring classification/profiling based on monitored movement patterns, such as targeted advertising, resource allocation, etc. To achieve this goal, we delegate part of the path extraction process to objects, …
Continuous Monitoring Of Spatial Queries In Wireless Broadcast Environments, Kyriakos Mouratidis, Spiridon Bakiras, Dimitris Papadias
Continuous Monitoring Of Spatial Queries In Wireless Broadcast Environments, Kyriakos Mouratidis, Spiridon Bakiras, Dimitris Papadias
Kyriakos MOURATIDIS
Wireless data broadcast is a promising technique for information dissemination that leverages the computational capabilities of the mobile devices in order to enhance the scalability of the system. Under this environment, the data are continuously broadcast by the server, interleaved with some indexing information for query processing. Clients may then tune in the broadcast channel and process their queries locally without contacting the server. Previous work on spatial query processing for wireless broadcast systems has only considered snapshot queries over static data. In this paper, we propose an air indexing framework that 1) outperforms the existing (i.e., snapshot) techniques in …
Optimal Matching Between Spatial Datasets Under Capacity Constraints, Hou U Leong, Kyriakos Mouratidis, Man Lung Yiu, Nikos Mamoulis
Optimal Matching Between Spatial Datasets Under Capacity Constraints, Hou U Leong, Kyriakos Mouratidis, Man Lung Yiu, Nikos Mamoulis
Kyriakos MOURATIDIS
Consider a set of customers (e.g., WiFi receivers) and a set of service providers (e.g., wireless access points), where each provider has a capacity and the quality of service offered to its customers is anti-proportional to their distance. The capacity constrained assignment (CCA) is a matching between the two sets such that (i) each customer is assigned to at most one provider, (ii) every provider serves no more customers than its capacity, (iii) the maximum possible number of customers are served, and (iv) the sum of Euclidean distances within the assigned provider-customer pairs is minimized. Although max-flow algorithms are applicable …
Continuous Spatial Assignment Of Moving Users, Leong Hou U, Kyriakos Mouratidis, Nikos Mamoulis
Continuous Spatial Assignment Of Moving Users, Leong Hou U, Kyriakos Mouratidis, Nikos Mamoulis
Kyriakos MOURATIDIS
Consider a set of servers and a set of users, where each server has a coverage region (i.e., an area of service) and a capacity (i.e., a maximum number of users it can serve). Our task is to assign every user to one server subject to the coverage and capacity constraints. To offer the highest quality of service, we wish to minimize the average distance between users and their assigned server. This is an instance of a well-studied problem in operations research, termed optimal assignment. Even though there exist several solutions for the static case (where user locations are fixed), …
Shortest Path Computation On Air Indexes, Georgios Kellaris, Kyriakos Mouratidis
Shortest Path Computation On Air Indexes, Georgios Kellaris, Kyriakos Mouratidis
Kyriakos MOURATIDIS
Shortest path computation is one of the most common queries in location-based services that involve transportation net- works. Motivated by scalability challenges faced in the mo- bile network industry, we propose adopting the wireless broad- cast model for such location-dependent applications. In this model the data are continuously transmitted on the air, while clients listen to the broadcast and process their queries locally. Although spatial problems have been considered in this environment, there exists no study on shortest path queries in road networks. We develop the rst framework to compute shortest paths on the air, and demonstrate the practicality and …
Preference Queries In Large Multi-Cost Transportation Networks, Kyriakos Mouratidis, Yimin Lin, Man Lung Yiu
Preference Queries In Large Multi-Cost Transportation Networks, Kyriakos Mouratidis, Yimin Lin, Man Lung Yiu
Kyriakos MOURATIDIS
Research on spatial network databases has so far considered that there is a single cost value associated with each road segment of the network. In most real-world situations, however, there may exist multiple cost types involved in transportation decision making. For example, the different costs of a road segment could be its Euclidean length, the driving time, the walking time, possible toll fee, etc. The relative significance of these cost types may vary from user to user. In this paper we consider such multi-cost transportation networks (MCN), where each edge (road segment) is associated with multiple cost values. We formulate …