Physical Sciences and Mathematics Commons^™

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 …

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 …

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 to …

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 is …

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

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

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) to …

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 step, …

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

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 compromised by …

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 …

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 …

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) is minimized. Thus, the CCA problem is …

Continuous Nearest Neighbor Monitoring In Road Networks, Kyriakos Mouratidis, Man Lung Yiu, Dimitris Papadias, Nikos Mamoulis

Kyriakos MOURATIDIS

Recent research has focused on continuous monitoring of nearest neighbors (NN) in highly dynamic scenarios, where the queries and the data objects move frequently and arbitrarily. All existing methods, however, assume the Euclidean distance metric. In this paper we study k-NN monitoring in road networks, where the distance between a query and a data object is determined by the length of the shortest path connecting them. We propose two methods that can handle arbitrary object and query moving patterns, as well as °uctuations of edge weights. The ¯rst one maintains the query results by processing only updates that may invalidate …

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), …

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

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

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

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 algorithm …

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 …

Global Dimension Of Ci: Compete Or Collaborate, Arden L. Bement Jr.

PPRI Digital Library

No abstract provided.

Spatial Semantics For Better Interoperability And Analysis: Challenges And Experiences In Building Semantically Rich Applications In Web 3.0, Amit P. Sheth

Kno.e.sis Publications

No abstract provided.

A Visual Approach To Automated Text Mining And Knowledge Discovery, Andrey A. Puretskiy

Doctoral Dissertations

The focus of this dissertation has been on improving the non-negative tensor factorization technique of text mining. The improvements have been made in both pre-processing and post-processing stages, with the goal of making the non-negative tensor factorization algorithm accessible to the casual user. The improved implementation allows the user to construct and modify the contents of the tensor, experiment with relative term weights and trust measures, and experiment with the total number of algorithm output features. Non-negative tensor factorization output feature production is closely integrated with a visual post-processing tool, FutureLens, that allows the user to perform in depth analysis …

Mobile Visibility Querying For Lbs, James Carswell, Keith Gardiner, Junjun Jin

Articles

This article describes research carried out in the area of mobile spatial interaction (MSI) and the development of a 3D mobile version of a 2D web-based directional query processor. The TellMe application integrates location (from GPS, GSM, WiFi) and orientation (from magnetometer/accelerometer) sensor technologies into an enhanced spatial query processing module capable of exploiting a mobile device’s position and orientation for querying real-world spatial datasets. This article outlines our technique for combining these technologies and the architecture needed to deploy them on a sensor enabled smartphone (i.e. Nokia Navigator 6210). With all these sensor technologies now available on off-the-shelf devices, …

Two Essays On The Accounting Treatment For Information Technology Expenditures, Kimberly Swanson Church

Graduate Theses and Dissertations

The current accounting measurement and reporting system is ill-equipped to provide intangible investment information that is decision useful for stakeholders in the information economy. Potentially relevant intangible items are not reported on the balance sheet, since current standards mandate the immediate expensing of these intangible items. Presumably FASB's uncertainty with the fundamental issues of extent and timing of future benefits to the firm has led to concerns with relevance, reliability, and objectivity of capitalizing some intangibles, which results in potential long term value generating expenditures being immediately expensed on the income statement. Prior research has demonstrated extent and timing of …

Sequence Alignment Based Analysis Of Player Behavior In Massively Multiplayer Online Role-Playing Games (Mmorpgs), Kyong Jin Shim, Jaideep Srivastava

Research Collection School Of Computing and Information Systems

This study proposes a sequence alignment-based behavior analysis framework (SABAF) developed for predicting inactive game players that either leave the game permanently or stop playing the game for a long period of time. Sequence similarity scores and derived statistics form profile databases of inactive players and active players from the past. SABAF uses global and local sequence alignment algorithms and a unique scoring scheme to measure similarity between activity sequences. SABAF is tested on the game player activity data of Ever Quest II, a popular massively multiplayer online role-playing game developed by Sony Online Entertainment. SABAF consists of the following …

Exploiting Intensity Inhomogeneity To Extract Textured Objects From Natural Scenes, Jundi Ding, Jialie Shen, Hwee Hwa Pang, Songcan Chen, Jingyu Yang

Research Collection School Of Computing and Information Systems

Extracting textured objects from natural scenes is a challenging task in computer vision. The main difficulties arise from the intrinsic randomness of natural textures and the high-semblance between the objects and the background. In this paper, we approach the extraction problem with a seeded region-growing framework that purely exploits the statistical properties of intensity inhomogeneity. The pixels in the interior of potential textured regions are first found as texture seeds in an unsupervised manner. The labels of the texture seeds are then propagated through their respective inhomogeneous neighborhoods, to eventually cover the different texture regions in the image. Extensive experiments …

Dynamic Indexing, Viswada Sripathi

UNLV Theses, Dissertations, Professional Papers, and Capstones

In this thesis, we report on index constructions for large document collections to facilitate the task of search and retrieval. We first report on classical static index construction methods and their shortcomings. We then report on dynamic index construction techniques and their effectiveness.

A Multi-User Steganographic File System On Untrusted Shared Storage, Jin Han, Meng Pan, Debin Gao, Hwee Hwa Pang

Research Collection School Of Computing and Information Systems

Existing steganographic file systems enable a user to hide the existence of his secret data by claiming that they are (static) dummy data created during disk initialization. Such a claim is plausible if the adversary only sees the disk content at the point of attack. In a multi-user computing environment that employs untrusted shared storage, however, the adversary could have taken multiple snapshots of the disk content over time. Since the dummy data are static, the differences across snapshots thus disclose the locations of user data, and could even reveal the user passwords. In this paper, we introduce a Dummy-Relocatable …

Japanese Kanji Suggestion Tool, Sujata Dongre

Master's Projects

Many times, we can see that if we enter a misspelled search term in any of the search engines like Google, it will provide some help with "Did you mean:...." In my project, I am providing some suggestions for the wrong Japanese text entered by a user.

The Japanese language has three types of writing styles - hiragana, katakana and the most difficult, kanji. A single kanji symbol may be used to write one or more different compound words. From the point of view of the reader, kanji symbols are said to have one or more different "readings." Hence, sometimes …