SIGMOD Record

Chúng tôi được cung cấp một cơ sở dữ liệu lớn về các giao dịch của khách hàng. Mỗi giao dịch bao gồm các mặt hàng mà một khách hàng đã mua trong một lần ghé thăm. Chúng tôi giới thiệu một thuật toán hiệu quả để sinh ra tất cả các quy tắc liên kết đáng kể giữa các mặt hàng trong cơ sở dữ liệu. Thuật toán này tích hợp quản lý bộ đệm và các kỹ thuật ước lượng và cắt tỉa mới. Chúng tôi cũng trình bày kết quả áp dụng thuật toán này cho dữ liệu bán hàng thu được từ một công ty bán lẻ lớn, cho thấy hiệu quả của thuật toán.

The widespread distribution and availability of small-scale sensors, actuators, and embedded processors is transforming the physical world into a computing platform. One such example is a sensor network consisting of a large number of sensor nodes that combine physical sensing capabilities such as temperature, light, or seismic sensors with networking and computation capabilities. Applications range from environmental control, warehouse inventory, and health care to military environments. Existing sensor networks assume that the sensors are preprogrammed and send data to a central frontend where the data is aggregated and stored for offline querying and analysis. This approach has two major drawbacks. First, the user cannot change the behavior of the system on the fly. Second, conservation of battery power is a major design factor, but a central system cannot make use of in-network programming, which trades costly communication for cheap local computation.In this paper, we introduce the Cougar approach to tasking sensor networks through declarative queries. Given a user query, a query optimizer generates an efficient query plan for in-network query processing, which can vastly reduce resource usage and thus extend the lifetime of a sensor network. In addition, since queries are asked in a declarative language, the user is shielded from the physical characteristics of the network. We give a short overview of sensor networks, propose a natural architecture for a data management system for sensor networks, and describe open research problems in this area.

Online social networks play a major role in the spread of information at very large scale. A lot of effort have been made in order to understand this phenomenon, ranging from popular topic detection to information diffusion modeling, including influential spreaders identification. In this article, we present a survey of representative methods dealing with these issues and propose a taxonomy that summarizes the state-of-the-art. The objective is to provide a comprehensive analysis and guide of existing efforts around information diffusion in social networks. This survey is intended to help researchers in quickly understanding existing works and possible improvements to bring.

Clustering is an unsupervised process since there are no predefined classes and no examples that would indicate grouping properties in the data set. The majority of the clustering algorithms behave differently depending on the features of the data set and the initial assumptions for defining groups. Therefore, in most applications the resulting clustering scheme requires some sort of evaluation as regards its validity. Evaluating and assessing the results of a clustering algorithm is the main subject of cluster validity. In this paper we present a review of the clustering validity and methods. More specifically, Part I of the paper discusses the cluster validity approaches based on external and internal criteria.

Xác thực kết quả phân cụm là một chủ đề quan trọng trong bối cảnh nhận dạng mẫu. Chúng tôi xem xét các phương pháp và hệ thống trong bối cảnh này. Trong phần đầu của bài báo này, chúng tôi trình bày các phương pháp kiểm tra tính hợp lệ của phân cụm dựa trên các tiêu chí nội tại và ngoại tại. Trong phần thứ hai, chúng tôi trình bày một cái nhìn tổng quan về các phương pháp tính hợp lệ phân cụm dựa trên các tiêu chí tương đối. Ngoài ra, chúng tôi cũng thảo luận về kết quả của một nghiên cứu thực nghiệm dựa trên các chỉ số hợp lệ nổi tiếng. Cuối cùng, bài báo minh họa những vấn đề còn thiếu được đề cập bởi các phương pháp gần đây và đề xuất các hướng nghiên cứu trong lĩnh vực này.

Decision support systems (DSS) and data warehousing workloads comprise an increasing fraction of the database market today. I/O capacity and associated processing requirements for DSS workloads are increasing at a rapid rate, doubling roughly every nine to twelve months [38]. In response to this increasing storage and computational demand, we present a computer architecture for decision support database servers that utilizes “intelligent” disks (IDISKs). IDISKs utilize low-cost embedded general-purpose processing, main memory, and high-speed serial communication links on each disk. IDISKs are connected to each other via these serial links and high-speed crossbar switches, overcoming the I/O bus bottleneck of conventional systems. By off-loading computation from expensive desktop processors, IDISK systems may improve cost-performance. More importantly, the IDISK architecture allows the processing of the system to scale with increasing storage demand.

Query languages for graph databases started to be investigated some 25 years ago. With much current data, such as linked data on the Web and social network data, being graph-structured, there has been a recent resurgence in interest in graph query languages. We provide a brief survey of many of the graph query languages that have been proposed, focussing on the core functionality provided in these languages. We also consider issues such as expressive power and the computational complexity of query evaluation.

Nhiều hệ thống cơ sở dữ liệu thương mại duy trì các biểu đồ để tóm tắt nội dung của các quan hệ và cho phép ước lượng hiệu quả kích thước kết quả truy vấn và chi phí kế hoạch truy cập. Mặc dù đã có nhiều loại biểu đồ được đề xuất trong quá khứ, nhưng chưa có một nghiên cứu hệ thống nào về tất cả các khía cạnh của biểu đồ, các lựa chọn có sẵn cho từng khía cạnh và tác động của những lựa chọn đó đến hiệu quả của biểu đồ. Trong bài báo này, chúng tôi cung cấp một phân loại các biểu đồ phản ánh tất cả các loại biểu đồ đã được đề xuất trước đó và chỉ ra nhiều khả năng mới. Chúng tôi giới thiệu các lựa chọn mới cho một số chiều của phân loại, và phát triển các loại biểu đồ mới bằng cách kết hợp các lựa chọn theo cách hiệu quả. Chúng tôi cũng cho thấy cách mà các kỹ thuật lấy mẫu có thể được sử dụng để giảm chi phí xây dựng biểu đồ. Cuối cùng, chúng tôi trình bày kết quả từ một nghiên cứu thực nghiệm về các loại biểu đồ được đề xuất trong ước lượng tính chọn lọc của các điều kiện phạm vi và xác định các loại biểu đồ có hiệu suất tổng thể tốt nhất.

Một tóm tắt phân vị xấp xỉ ∈ của một chuỗi N phần tử là một cấu trúc dữ liệu có thể trả lời các truy vấn về phân vị đối với chuỗi với độ chính xác là ∈ N .

Chúng tôi trình bày một thuật toán trực tuyến mới để tính toán các tóm tắt phân vị xấp xỉ ∈ của các chuỗi dữ liệu rất lớn. Thuật toán này có yêu cầu không gian trong trường hợp tồi tệ nhất là Ο (1÷∈ log(∈ N )). Kết quả này tốt hơn so với kết quả tốt nhất trước đây là Ο (1÷∈ log ² (∈ N )). Hơn nữa, trái ngược với các thuật toán xác định trước đây, thuật toán của chúng tôi không yêu cầu kiến thức a priori về độ dài của chuỗi đầu vào.

Cuối cùng, các giới hạn không gian thực tế thu được trên dữ liệu thử nghiệm tốt hơn đáng kể so với các đảm bảo trường hợp tồi tệ nhất của thuật toán của chúng tôi cũng như các yêu cầu không gian quan sát được của các thuật toán trước đó.