Browsing by Author "TOK, Wee Hyong"

Now showing 1 - 4 of 4
  • No Thumbnail Available
    Item
    An Application of Constraint Programming to Mobile Data
    (2005-10-19) BRESSAN, Stephane; TOK, Wee Hyong; PRESTWICH, Steven
    Given the current ubiquity of wireless networks and mobile devices, data must be disseminated to a large number of these devices in an effective and efficient manner. A promising technique for such applications is data broadcasting. We introduce a new optimization problem derived from mobile data broadcasting applications. A single broadcaster transmits pages of data in sequence in response to requests from multiple clients, each asking for different subsets of a set of available pages. A transmitted page can be read by any number of clients, and we aim to minimise the total time taken to transmit all pages. Users impose additional constraints on how long they are willing to wait between pages, because of limited power supply in mobile devices. This problem is closely related to the multiple sequence alignment problem from bioinformatics. We present a first constraint model for this problem, designed for use with randomized local search algorithms.
  • No Thumbnail Available
    Item
    Non-blocking Spatial Join
    (2007-07-25) TOK, Wee Hyong; BRESSAN, Stephane; LEE, Mong Li
    We propose and study sequential non-blocking algorithms for the processing of spatial joins on continuous data streams with unpredictable arrival rates or on large collections of spatial data that are not indexed. Given two sets of spatial data represented by their bounding boxes, the algorithms immediately and continuously compute and output the pairs of data from each set whose bounding boxes intersect. The different algorithms we propose take advantage of different possible characteristics of the data such as clustering of the input to build indexes or synopses to accelerate the production of results. We comparatively analyze the performance of the proposed algorithms using several synthetic and realistic data sets.
  • No Thumbnail Available
    Item
    A Stratified Approach to Progressive Approximate Joins
    (2007-09-24) TOK, Wee Hyong; BRESSAN, Stéphane; LEE, Mong-Li
    Users often do not require a complete answer to their query but rather only a sample. They expect the sample to be either the largest possible or the most representative (or both) given the resources available. We call the query processing techniques that deliver such results approximate. Process- ing of queries to streams of data is said to be progressive when it can continuously produce results as data arrives. In this paper, we are interested in the progressive and approxi- mate processing of queries to data streams when processing is limited to main memory. In particular, we study one of the main building blocks of such processing: the progressive approximate join. We devise and present several novel progressive approximate join algorithms. We empirically evaluate the performance of our algorithms and compare them with those of algorithms based on existing techniques. In particu- lar we study the trade-off between maximization throughput and maximization of representativeness of the sample.
  • No Thumbnail Available
    Item
    Twig'n Join: Progressive Query Processing of Multiple XML Streams
    (2007-09-03T08:58:02Z) TOK, Wee Hyong; BRESSAN, Stephane; LEE, Mong-Li
    We propose a practical approach to the progressive processing of (FWR) XQuery queries on multiple XML streams, called Twig.n Join (or TnJ). The query is decomposed into a query plan combining several Twig queries on the individual streams, followed by a join and a final Twig query. The processing is itself accordingly decomposed into three pipelined stages progressively producing streams of XML fragments. We use the recently proposed TwigM algorithm for the progressive evaluation of Twig queries. We devise an original progressive join algorithm for the XML fragments leveraging our previous work on relational result-rate based progressive joins. In addition, we propose a multi-way XML value join algorithm, which uses a result-oriented approach to determine the probing sequence for multiple XML streams. We comparatively evaluate the performance of the Twig.n Join variants using both synthetic and real-life data from standard XML query processing benchmarks. We show that Twig.n Join with a result-rate based approach is most effective and efficient.