Open Access. Powered by Scholars. Published by Universities.®

Physical Sciences and Mathematics Commons

Open Access. Powered by Scholars. Published by Universities.®

171,861 Full-Text Articles 205,627 Authors 37,243,081 Downloads 372 Institutions

All Articles in Physical Sciences and Mathematics

Faceted Search

171,861 full-text articles. Page 4042 of 4453.

Continuous Monitoring Of Spatial Queries In Wireless Broadcast Environments, Kyriakos MOURATIDIS, Spiridon Bakiras, Dimitris Papadias 2010 Singapore Management University

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 ...


Authenticating The Query Results Of Text Search Engines, Hwee Hwa PANG, Kyriakos MOURATIDIS 2010 Singapore Management University

Authenticating The Query Results Of Text Search Engines, Hwee Hwa Pang, Kyriakos Mouratidis

Kyriakos MOURATIDIS

The number of successful attacks on the Internet shows that it is very difficult to guarantee the security of online search engines. A breached server that is not detected in time may return incorrect results to the users. To prevent that, we introduce a methodology for generating an integrity proof for each search result. Our solution is targeted at search engines that perform similarity-based document retrieval, and utilize an inverted list implementation (as most search engines do). We formulate the properties that define a correct result, map the task of processing a text search query to adaptations of existing threshold-based ...


Computing Medoids In Large Spatial Datasets, Kyriakos MOURATIDIS, Dimitris Papadias, Spiros Papadimitriou 2010 Singapore Management University

Computing Medoids In Large Spatial Datasets, Kyriakos Mouratidis, Dimitris Papadias, Spiros Papadimitriou

Kyriakos MOURATIDIS

No abstract provided.


Efficient Evaluation Of Continuous Text Seach Queries, Kyriakos MOURATIDIS, Hwee Hwa PANG 2010 Singapore Management University

Efficient Evaluation Of Continuous Text Seach Queries, Kyriakos Mouratidis, Hwee Hwa Pang

Kyriakos MOURATIDIS

Consider a text filtering server that monitors a stream of incoming documents for a set of users, who register their interests in the form of continuous text search queries. The task of the server is to constantly maintain for each query a ranked result list, comprising the recent documents (drawn from a sliding window) with the highest similarity to the query. Such a system underlies many text monitoring applications that need to cope with heavy document traffic, such as news and email monitoring.In this paper, we propose the first solution for processing continuous text queries efficiently. Our objective is ...


A Fair Assignment Algorithm For Multiple Preference Queries, Leong Hou U, Nikos Mamoulis, Kyriakos Mouratidis 2010 University of Hong Kong

A Fair Assignment Algorithm For Multiple Preference Queries, Leong Hou U, Nikos Mamoulis, Kyriakos Mouratidis

Kyriakos MOURATIDIS

Consider an internship assignment system, where at the end of each academic year, interested university students search and apply for available positions, based on their preferences (e.g., nature of the job, salary, office location, etc). In a variety of facility, task or position assignment contexts, users have personal preferences expressed by different weights on the attributes of the searched objects. Although individual preference queries can be evaluated by selecting the object in the database with the highest aggregate score, in the case of multiple simultaneous requests, a single object cannot be assigned to more than one users. The challenge ...


Conceptual Partitioning: An Efficient Method For Continuous Nearest Neighbor Monitoring, Kyriakos MOURATIDIS, Marios Hadjieleftheriou, Dimitris Papadias 2010 Hong Kong University of Science and Technology

Conceptual Partitioning: An Efficient Method For Continuous Nearest Neighbor Monitoring, Kyriakos Mouratidis, Marios Hadjieleftheriou, Dimitris Papadias

Kyriakos MOURATIDIS

Given a set of objects P and a query point q, a k nearest neighbor (k-NN) query retrieves the k objects in P that lie closest to q. Even though the problem is well-studied for static datasets, the traditional methods do not extend to highly dynamic environments where multiple continuous queries require real-time results, and both objects and queries receive frequent location updates. In this paper we propose conceptual partitioning (CPM), a comprehensive technique for the efficient monitoring of continuous NN queries. CPM achieves low running time by handling location updates only from objects that fall in the vicinity of ...


An Incremental Threshold Method For Continuous Text Search Queries, Kyriakos MOURATIDIS, Hwee Hwa PANG 2010 Singapore Management University

An Incremental Threshold Method For Continuous Text Search Queries, Kyriakos Mouratidis, Hwee Hwa Pang

Kyriakos MOURATIDIS

A text filtering system monitors a stream of incoming documents, to identify those that match the interest profiles of its users. The user interests are registered at a server as continuous text search queries. The server constantly maintains for each query a ranked result list, comprising the recent documents (drawn from a sliding window) with the highest similarity to the query. Such a system underlies many text monitoring applications that need to cope with heavy document traffic, such as news and email monitoring. In this paper, we propose the first solution for processing continuous text queries efficiently. Our objective is ...


Spatial Cloaking Revisited: Distinguishing Information Leakage From Anonymity, Kar Way TAN, Yimin LIN, Kyriakos MOURATIDIS 2010 Singapore Management University

Spatial Cloaking Revisited: Distinguishing Information Leakage From Anonymity, Kar Way Tan, Yimin Lin, Kyriakos Mouratidis

Kyriakos MOURATIDIS

Location-based services (LBS) are receiving increasing popularity as they provide convenience to mobile users with on-demand information. The use of these services, however, poses privacy issues as the user locations and queries are exposed to untrusted LBSs. Spatial cloaking techniques provide privacy in the form of k-anonymity; i.e., they guarantee that the (location of the) querying user u is indistinguishable from at least k-1 others, where k is a parameter specified by u at query time. To achieve this, they form a group of k users, including u, and forward their minimum bounding rectangle (termed anonymzing spatial region, ASR ...


Group Nearest Neighbor Queries, Dimitris PAPADIAS, Qiongmao SHEN, Yufei TAO, Kyriakos MOURATIDIS 2010 Hong Kong University of Science and Technology

Group Nearest Neighbor Queries, Dimitris Papadias, Qiongmao Shen, Yufei Tao, Kyriakos Mouratidis

Kyriakos MOURATIDIS

Given two sets of points P and Q, a group nearest neighbor (GNN) query retrieves the point(s) of P with the smallest sum of distances to all points in Q. Consider, for instance, three users at locations q1 , q2 and q3 that want to find a meeting point (e.g., a restaurant); the corresponding query returns the data point p that minimizes the sum of Euclidean distances |pqi| for 1 ≤i ≤3. Assuming that Q fits in memory and P is indexed by an R-tree, we propose several algorithms for finding the group nearest neighbors efficiently. As a second ...


Medoid Queries In Large Spatial Databases, Kyriakos MOURATIDIS, Dimitris Papadias, Spiros Papadimitriou 2010 Hong Kong University of Science and Technology

Medoid Queries In Large Spatial Databases, Kyriakos Mouratidis, Dimitris Papadias, Spiros Papadimitriou

Kyriakos MOURATIDIS

Assume that a franchise plans to open k branches in a city, so that the average distance from each residential block to the closest branch is minimized. This is an instance of the k-medoids problem, where residential blocks constitute the input dataset and the k branch locations correspond to the medoids. Since the problem is NP-hard, research has focused on approximate solutions. Despite an avalanche of methods for small and moderate size datasets, currently there exists no technique applicable to very large databases. In this paper, we provide efficient algorithms that utilize an existing data-partition index to achieve low CPU ...


Efficient Verification Of Shortest Path Search Via Authenticated Hints, Man Lung YIU, Yimin LIN, Kyriakos MOURATIDIS 2010 Hong Kong Polytechnic University

Efficient Verification Of Shortest Path Search Via Authenticated Hints, Man Lung Yiu, Yimin Lin, Kyriakos Mouratidis

Kyriakos MOURATIDIS

Shortest path search in transportation networks is unarguably one of the most important online search services nowadays (e.g., Google Maps, MapQuest, etc), with applications spanning logistics, spatial optimization, or everyday driving decisions. Often times, the owner of the road network data (e.g., a transport authority) provides its database to third-party query services, which are responsible for answering shortest path queries posed by their clients. The issue arising here is that a query service might be returning sub-optimal paths either purposely (in order to serve its own purposes like computational savings or commercial reasons) or because it has been ...


Constrained Shortest Path Computation, Manolis TERROVITIS, Spiridon BAKIRAS, Dimitris PAPADIAS, Kyriakos MOURATIDIS 2010 Hong Kong University of Science and Technology

Constrained Shortest Path Computation, Manolis Terrovitis, Spiridon Bakiras, Dimitris Papadias, Kyriakos Mouratidis

Kyriakos MOURATIDIS

This paper proposes and solves a-autonomy and k-stops shortest path problems in large spatial databases. Given a source s and a destination d, an aautonomy query retrieves a sequence of data points connecting s and d, such that the distance between any two consecutive points in the path is not greater than a. A k-stops query retrieves a sequence that contains exactly k intermediate data points. In both cases our aim is to compute the shortest path subject to these constraints. Assuming that the dataset is indexed by a data-partitioning method, the proposed techniques initially compute a sub-optimal path by ...


Capacity Constrained Assignment In Spatial Databases, Hou U LEONG, Man Lung YIU, Kyriakos MOURATIDIS, Nikos MAMOULIS 2010 University of Hong Kong

Capacity Constrained Assignment In Spatial Databases, Hou U Leong, Man Lung Yiu, Kyriakos Mouratidis, Nikos Mamoulis

Kyriakos MOURATIDIS

Given a point set P of customers (e.g., WiFi receivers) and a point set Q of service providers (e.g., wireless access points), where each q 2 Q has a capacity q.k, the capacity constrained assignment (CCA) is a matching M Q × P such that (i) each point q 2 Q (p 2 P) appears at most k times (at most nce) in M, (ii) the size of M is maximized (i.e., it comprises min{|P|,P q2Q q.k} pairs), and (iii) the total assignment cost (i.e., the sum of Euclidean distances within all pairs ...


Continuous Spatial Assignment Of Moving Users, Leong Hou U, Kyriakos MOURATIDIS, Nikos Mamoulis 2010 University of Hong Kong

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 ...


Continuous Monitoring Of Spatial Queries, Kyriakos MOURATIDIS 2010 Singapore Management University

Continuous Monitoring Of Spatial Queries, Kyriakos Mouratidis

Kyriakos MOURATIDIS

No abstract provided.


Continuous Monitoring Of Top-K Queries Over Sliding Windows, Kyriakos MOURATIDIS, Spiridon BAKIRAS, Dimitris PAPADIAS 2010 Singapore Management University

Continuous Monitoring Of Top-K Queries Over Sliding Windows, Kyriakos Mouratidis, Spiridon Bakiras, Dimitris Papadias

Kyriakos MOURATIDIS

Given a dataset P and a preference function f, a top-k query retrieves the k tuples in P with the highest scores according to f. Even though the problem is well-studied in conventional databases, the existing methods are inapplicable to highly dynamic environments involving numerous long-running queries. This paper studies continuous monitoring of top-k queries over a fixed-size window W of the most recent data. The window size can be expressed either in terms of the number of active tuples or time units. We propose a general methodology for top-k monitoring that restricts processing to the sub-domains of the workspace ...


Shortest Path Computation On Air Indexes, Georgios KELLARIS, Kyriakos MOURATIDIS 2010 Singapore Management University

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 ...


A Threshold-Based Algorithm For Continuous Monitoring Of K Nearest Neighbors, Kyriakos MOURATIDIS, Dimitris Papadias, Spiridon Bakiras, Yufei TAO 2010 Singapore Management University

A Threshold-Based Algorithm For Continuous Monitoring Of K Nearest Neighbors, Kyriakos Mouratidis, Dimitris Papadias, Spiridon Bakiras, Yufei Tao

Kyriakos MOURATIDIS

Assume a set of moving objects and a central server that monitors their positions over time, while processing continuous nearest neighbor queries from geographically distributed clients. In order to always report up-to-date results, the server could constantly obtain the most recent position of all objects. However, this naïve solution requires the transmission of a large number of rapid data streams corresponding to location updates. Intuitively, current information is necessary only for objects that may influence some query result (i.e., they may be included in the nearest neighbor set of some client). Motivated by this observation, we present a threshold-based ...


Preference Queries In Large Multi-Cost Transportation Networks, Kyriakos MOURATIDIS, Yimin LIN, Man Lung YIU 2010 Singapore Management University

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 ...


Crystalline Order On Catenoidal Capillary Bridges, Mark Bowick, Zhenwei Yao 2010 Department of Physics, Syracuse University, Syracuse, NY

Crystalline Order On Catenoidal Capillary Bridges, Mark Bowick, Zhenwei Yao

Physics

We study the defect structure of crystalline particle arrays on negative Gaussian curvature capillary bridges with vanishing mean curvature (catenoids). The threshold aspect ratio for the appearance of isolated disclinations is found and the optimal positions for dislocations determined. We also discuss the transition from isolated disclinations to scars as particle number and aspect ratio are varied.


Digital Commons powered by bepress