The problem of recommending items to users is of high practical importance. For instance, many web services try to find relevant recommendations for the users, e.g., finding relevant movies, social-media friends, restaurants, shopping items, etc. The expansion of the Web and the ever-growing number of people who use web services render the problem of recommendation challenging. The Locality Sensitive Hashing (LSH, for short) is the most known scalable technique for nearest-neighbor search in high dimensional data, and hence the LSH is widely used in most industrial recommendation systems. This paper presents an implementation of the LSH using Google's MapReduce engine. We apply the LSH to a real case study at Google, where we recommend for each web-host a set of outlinks based on the outlink similarity amongst the web-hosts. We identify some performance limitations of the LSH that occur due to specific properties in the data, and that become significant when the scale of the data is large. Furthermore, we present SHRec, a novel technique for scalable recommendation that addresses these performance limitations. Based on real deployment of both SHRec and LSH on Google's infrastructure, and using real data of the crawled Web at Google, where a sample host-level graph of 1.5 Billion web-hosts is extracted, we demonstrate that SHRec is more scalable than LSH. In particular, we show that SHRec is one order of magnitude faster than LSH while achieving better recommendation quality.

A sliding window join (SWJoin) is becoming an integral operation in every stream data management system. In some streaming applications the increasing volume of streamed data as well as the multiplicity of concurrent queries requires an adaptive SWJoin algorithm for the limited memory resources. Previous algorithms of SWJoin address the memory limitation by exploiting external-memory resources while imposing timely ordered arrival of input data streams. In this paper we propose an external-memory sliding-window join algorithm (EM-SWJoin) that addresses general arrival patterns of input streams and exploits disk- based data structures. The algorithm runs in two phases. The first phase partially joins the arriving data of one stream with the memory-resident data of the other streams. The second phase completes the processing of the partially joined data by considering the disk-resident data from the corresponding streams. Swapping from one phase to the other improves the response time of the input data. A comparative study between EM-SWJoin and other related algorithms illustrates the superiority of the proposed algorithm.

Two research efforts have been conducted to realize sliding-window queries in data stream management systems, namely, query revaluation and incremental evaluation. In the query reevaluation method, two consecutive windows are processed independently of each other. On the other hand, in the incremental evaluation method, the query answer for a window is obtained incrementally from the answer of the preceding window. In this paper, we focus on the incremental evaluation method. Two approaches have been adopted for the incremental evaluation of sliding-window queries, namely, the input-triggered approach and the negative tuples approach. In the input-triggered approach, only the newly inserted tuples flow in the query pipeline and tuple expiration is based on the timestamps of the newly inserted tuples. On the other hand, in the negative tuples approach, tuple expiration is separated from tuple insertion where a tuple flows in the pipeline for every inserted or expired tuple. The negative tuples approach avoids the unpredictable output delays that result from the input-triggered approach. However, negative tuples double the number of tuples through the query pipeline, thus reducing the pipeline bandwidth. Based on a detailed study of the incremental evaluation pipeline, we classify the incremental query operators into two classes according to whether an operator can avoid the processing of negative tuples or not. Based on this classification, we present several optimization techniques over the negative tuples approach that aim to reduce the overhead of processing negative tuples while avoiding the output delay of the query answer. A detailed experimental study, based on a prototype system implementation, shows the performance gains over the input-triggered approach of the negative tuples approach when accompanied with the proposed optimizations

Mechanisms to efficiently and effectively transmit up-todate information to clients are of significant interest. Broadcast-based scheduling in hierarchical data dissemination systems are under reported in the literature. In these systems a primary server accepts updates that are broadcast to secondary servers and then to a population of clients upon requests. This paper focuses on data dissemination with update propagation at the primary server side. Our initial study shows that at high update rates, a straightforward broadcast scheduler that ignores clients' access patterns can provide clients with outdated information more than 80% of the time. We propose three broadcast scheduling algorithms that primarily differ in how data dissemination with update propagation is guided at the primary and secondary servers. We present mechanisms based on real and predicted clients' access patterns. We evaluate the new scheduling algorithms by running an extensive set of experiments. The performance study illustrates that the third algorithm, which depends on predictive scheduling at both the primary and the secondary servers, provides the best response time and the reception of up-to-date information.

As information acquisition and processing applications take greater roles in our everyday life, database management systems are growing in importance. Database management systems have traditionally exhibited poor cache performance and large memory footprints, therefore performing only at a fraction of their ideal execution and exhibiting low processor utilization. Previous research has studied the memory system of database management systems (DBMSs) on research-based simultaneous multithreading (SMT) processors. Several differences have been noted between the real hyper-threaded architecture implemented by the Intel Pentium 4 and the earlier SMT research architectures. Therefore, it is important to study and analyze the performance of modern DBMSs on real SMT processors. This paper characterizes the performance of a prototype open-source DBMS running TPC-C-equivalent benchmark queries on an Intel Pentium 4 hyper-threading processor. We use the performance hardware counters provided by the Pentium 4 to evaluate the micro-architecture and study the memory system behavior of each query running on the data management system. Our results show a performance improvement of up to 1.16 due to hyperthreading

Many publish/subscribe systems have been built using wireless sensor networks, WSNs, deployed for real-world environmental data collection, security monitoring, and object tracking. However, research efforts on WSN-based publish/subscribe systems have largely focused on routing algorithms leaving data management issues mostly untouched. This paper considers a publish/subscribe system built on top of a sensor network that monitors the occurrences of phenomena. In quest for explanations to the occurrence of a phenomenon, a subscriber poses one-time queries to the sensor network for sensor readings taken seconds or minutes before the reported phenomenon occurred. These types of queries cannot be satisfied by subscriptions since subscriptions are only effective in delivering streams of new phenomena. To efficiently answer such queries, it is imperative that a data farm of sensor readings be cultivated within WSNs. This paper proposes a new algorithm for archiving sensor readings on data farm that leverages the non-volatile memory of sensor nodes in the network. The proposed algorithm takes advantage of the memory space on nodes that have low probabilities of detecting phenomena. By running an extensive set of simulation experiments, the performance results show that the proposed algorithm can provide 32.9% memory gain and 81.8% low communication overhead when compared to an approach in which nodes use only their own physical memory

We present the demonstration of the design of "STEAM", Purdue Boiler Makers' stream database system that allows for the processing of continuous and snap-shot queries over data streams. Specifically, the demonstration focuses on the query processing engine, "Nile". Nile extends the query processor engine of an object-relational database management system, PREDATOR, to process continuous queries over data streams. Nile supports extended SQL operators that handle sliding-window execution as an approach to restrict the size of the stored state in operators such as join.

The widespread use of sensor networks presents revolutionary opportunities for life and environmental science applications. Many of these applications involve continuous queries that require the tracking, monitoring, and correlation of multi-sensor data that represent moving objects. We propose to answer these queries using a multi-way stream window join operator. This form of join over multi-sensor data must cope with the infinite nature of sensor data streams and the delays in network transmission. The paper introduces a class of join algorithms, termed W-join, for joining multiple infinite data streams. W-join addresses the infinite nature of the data streams by joining stream data items that lie within a sliding window and that match a certain join condition. W-join can be used to track the motion of a moving object or detect the propagation of clouds of hazardous material or pollution spills over time in a sensor network environment. We describe two new algorithms for W-join, and address variations and local/global optimizations related to specifying the nature of the window constraints to fulfill the posed queries. The performance of the proposed algorithms are studied experimentally in a prototype stream database system, using synthetic data streams and real time-series data. Tradeoffs of the proposed algorithms and their advantages and disadvantages are highlighted, given variations in the aggregate arrival rates of the input data streams and the desired response times per query.

In our project, we are adopting a new approach for handling video data. We view the video as a well-defined data type with its own description, parameters and applicable methods. The system is based on PREDATOR, an open-source object-relational DBMS. PREDATOR uses Shore as the underlying storage manager. Supporting video operations (storing, searching-by-content and streaming) and new query types (query-by-example and multi-feature similarity searching) requires major changes in many of the traditional system components. More specifically, the storage and buffer manager has to deal with huge volumes of data with real-time constraints. Query processing has to consider the video methods and operators in generating, optimizing and executing the query plans.

In this paper we propose efficient buffer prefetching and replacement policies for continuous-media servers that support content-based search and retrieval. The new policies are based on the knowledge collected from the content-based search manager and the streaming manager. We show that by integrating the knowledge from the search and streaming components, we can achieve better caching of media streams, thus minimizing initial latency and reducing disk I/O. We test the search-based policies on a prototype video database system developed at Purdue University. The results show that initial latency is reduced on the average by 20%, compared to the traditional policies.

A novel approach for modeling access control in video databases is presented. The proposed access control mechanism uses both the semantics and the structural composition of video data. The unit of authorization, a video element, can either be a sequence of video frames or a video object that appears as part of a frame, e.g., the face of an anonymous person in an interview. The components of the access control model are the video elements, the potential users, and the mode of operation, e.g., viewing, or editing. Video elements are specied either explicitly by their identiers or implicitly by their semantic contents, while users are characterized by the user credentials. An algorithm is presented that determines the authorized portions of a video that a given user may acquire, given the user's credentials, the video content descriptions, and the type of requested video operations. The description of the implementation of a prototype MPEG-2 based video database system with access control are also presented. 1.