Browsing by Author "PAPADIAS, Dimitris"

Now showing 1 - 2 of 2
  • No Thumbnail Available
    Item
    Minimizing the Communication Cost for Continuous Skyline Maintenance
    (2008-05-29) ZHANG, Zhenjie; CHENG, Reynold; PAPADIAS, Dimitris; TUNG, Anthony K.H.
    Numerous algorithms in the recent database literature deal with variants of skyline queries in different problem settings. However, the existing work focuses on optimizing the processing cost. This paper aims at minimization of the communication overhead in client-server architectures, where a server continuously maintains the skyline of dynamic objects. Our first contribution is a Filter method that avoids transmission of updates from objects that cannot influence the skyline. Specifically, each object is assigned a filter so that it needs to issue an update only if it violates its filter. The Filter method achieves significant savings over the naive approach of transmitting all updates. Going one step further, we introduce the concept of frequent skyline query over a sliding window (FSQW). The motivation is that snapshot skylines are not very useful in streaming environments because they keep changing over time. Instead, FSQW reports the objects that appear in the skylines of at least ? of the s most recent times- tamps. The Filter method can be easily adapted to FSQW processing, however, with potentially high overhead for large and frequently updated datasets. To further reduce the communication cost, we propose a Sampling method, which returns approximate FSQW results without computing each snapshot skyline. Finally, we integrate the Filter and Sampling methods in a Hybrid approach that combines their individual advantages. We evaluate our techniques with extensive experiments.
  • No Thumbnail Available
    Item
    Preserving Anonymity in Location Based Services
    (2006-06-12) KALNIS, Panos; GHINITA, Gabriel; MOURATIDIS, Kyriakos; PAPADIAS, Dimitris
    The increasing trend of embedding positioning capabilities (e.g., GPS) in mobile devices facilitates the widespread use of Location Based Services. For such applications to succeed, the privacy and confidentiality issues are of paramount importance. Existing techniques, like encryption, safeguard the communication channel from eavesdroppers. Nevertheless, the queries themselves may disclose the physical location, identity and habits of the user. In this paper, we present a framework for preserving the anonymity of users issuing spatial queries to Location Based Services. We propose transformations based on the well-established K-anonymity technique to compute exact answers for Range and Nearest Neighbor queries, without revealing sensitive information about the user. Our methods optimize the entire process of anonymizing the requests and processing the transformed spatial queries. Extensive experimental studies suggest that our methods are applicable to real-life scenarios with numerous mobile users.