Communications of the ACM

Mặc dù việc sử dụng máy tính cá nhân tương đối phổ biến, nhưng trong các cuộc họp, chúng ta thường để chúng lại phía sau. Tại Xerox PARC, một phòng họp thử nghiệm có tên là Colab đã được tạo ra để nghiên cứu hỗ trợ máy tính trong việc giải quyết vấn đề hợp tác trong các cuộc họp trực tiếp. Mục tiêu lâu dài là hiểu cách xây dựng các công cụ máy tính nhằm làm cho các cuộc họp trở nên hiệu quả hơn.

Bài báo này phát triển cây tìm kiếm nhị phân đa chiều (hay còn gọi là cây k-d, trong đó k là số chiều của không gian tìm kiếm) như một cấu trúc dữ liệu để lưu trữ thông tin được truy xuất thông qua các tìm kiếm liên kết. Cây k-d được định nghĩa và các ví dụ được đưa ra. Nó cho thấy khá hiệu quả trong yêu cầu lưu trữ. Một lợi thế đáng kể của cấu trúc này là một cấu trúc dữ liệu duy nhất có thể xử lý nhiều loại truy vấn một cách rất hiệu quả. Nhiều thuật toán tiện ích đã được phát triển; thời gian chạy trung bình đã chứng minh của chúng trong một tệp chứa n bản ghi là: chèn, O(log n); xóa gốc, O(n^(k-1)/k); xóa một nút ngẫu nhiên, O(log n); và tối ưu hóa (đảm bảo hiệu suất logarithmic của các tìm kiếm), O(n log n). Các thuật toán tìm kiếm được đưa ra cho các truy vấn tìm kiếm khớp một phần với t khóa được chỉ định [thời gian chạy tối đa đã chứng minh là O(n^(k-t)/k)] và cho các truy vấn hàng xóm gần nhất [thời gian chạy trung bình quan sát được thực nghiệm là O(log n)] . Những hiệu suất này vượt xa so với các thuật toán tốt nhất hiện tại cho những nhiệm vụ này. Một thuật toán được trình bày để xử lý bất kỳ truy vấn giao nhau tổng quát nào. Trọng tâm chính của bài báo này là lý thuyết. Tuy nhiên, chúng tôi cảm thấy rằng cây k-d có thể rất hữu ích trong nhiều ứng dụng, và các ví dụ về các ứng dụng tiềm năng được đưa ra.

Trong một hệ thống truy xuất tài liệu, hoặc môi trường so khớp mẫu khác, nơi mà các thực thể lưu trữ (tài liệu) được so sánh với nhau hoặc với các mẫu đến (yêu cầu tìm kiếm), có vẻ như không gian lập chỉ mục (thuộc tính) tốt nhất là nơi mà mỗi thực thể cách xa nhau nhất có thể; trong những trường hợp này, giá trị của một hệ thống lập chỉ mục có thể được diễn đạt như một hàm của mật độ không gian của đối tượng; đặc biệt, hiệu suất truy xuất có thể tương quan nghịch với mật độ không gian. Một phương pháp dựa trên các phép toán mật độ không gian được sử dụng để chọn một từ vựng lập chỉ mục tối ưu cho một tập hợp các tài liệu. Các kết quả đánh giá điển hình được trình bày, cho thấy tính hữu ích của mô hình.

Xóa bỏ những mây mù khỏi tiềm năng thực sự và những trở ngại mà khả năng tính toán này gây ra.

Một phương pháp mã hóa được trình bày với đặc điểm mới là việc công khai một khóa mã hóa không tiết lộ khóa giải mã tương ứng. Điều này có hai hệ quả quan trọng: (1) Không cần đến những người chuyển phát hoặc các phương tiện bảo mật khác để truyền tải khóa, vì một thông điệp có thể được mã hóa bằng khóa mã hóa được công khai bởi người nhận mong muốn. Chỉ có người đó có thể giải mã được thông điệp, vì chỉ có họ biết khóa giải mã tương ứng. (2) Một thông điệp có thể được "ký" bằng khóa giải mã được giữ bí mật. Bất kỳ ai cũng có thể xác minh chữ ký này bằng cách sử dụng khóa mã hóa đã được công khai. Chữ ký không thể bị giả mạo và người ký không thể phủ nhận tính hợp lệ của chữ ký của mình. Điều này có áp dụng rõ ràng trong các hệ thống "thư điện tử" và "chuyển khoản điện tử". Một thông điệp được mã hóa bằng cách đại diện cho nó như một số M, nâng M lên một số mũ e được chỉ định công khai, và sau đó lấy phần dư khi kết quả được chia cho một tích số công khai được chỉ định, n , của hai số nguyên tố bí mật lớn p và q. Việc giải mã tương tự; chỉ sử dụng một số mũ bí mật khác, d, trong đó e * d ≡ 1(mod (p - 1) * (q - 1)). Sự an toàn của hệ thống phần nào dựa vào độ khó của việc phân tích thừa số của số chia công khai, n .

Trong bài báo này, chúng tôi trình bày cách chia dữ liệu D thành n phần sao cho D có thể dễ dàng tái tạo từ bất kỳ k phần nào, nhưng ngay cả khi có đầy đủ thông tin về k - 1 phần thì cũng không tiết lộ bất kỳ thông tin nào về D . Kỹ thuật này cho phép xây dựng các sơ đồ quản lý khóa mạnh mẽ cho các hệ thống mã hóa có thể hoạt động an toàn và đáng tin cậy ngay cả khi các sự cố phá hủy một nửa số phần và các lỗ hổng bảo mật tiết lộ tất cả ngoại trừ một trong các phần còn lại.

Bởi vì câu có ý nghĩa được tạo thành từ các từ có nghĩa, bất kỳ hệ thống nào mong muốn xử lý ngôn ngữ tự nhiên như con người phải có thông tin về các từ và ý nghĩa của chúng. Thông tin này thường được cung cấp thông qua từ điển, và các từ điển có thể đọc được bằng máy hiện nay đã trở nên phổ biến. Nhưng các mục từ điển đã được phát triển vì mục đích thuận tiện cho người đọc, không phải cho máy móc. WordNet ¹ cung cấp một sự kết hợp hiệu quả hơn giữa thông tin từ điển truyền thống và công nghệ máy tính hiện đại. WordNet là một cơ sở dữ liệu từ vựng trực tuyến được thiết kế để sử dụng dưới sự kiểm soát của chương trình. Các danh từ, động từ, tính từ và trạng từ tiếng Anh được tổ chức thành các tập hợp đồng nghĩa, mỗi tập hợp đại diện cho một khái niệm từ vựng. Các mối quan hệ ngữ nghĩa liên kết các tập hợp đồng nghĩa [4].

MapReduce là một mô hình lập trình và một cách triển khai liên quan để xử lý và sinh ra các tập dữ liệu lớn, phù hợp với nhiều nhiệm vụ trong thực tế. Người dùng xác định phép tính theo các hàm map và reduce, và hệ thống thực thi nền tảng tự động phân tán phép tính trên các cụm máy lớn, xử lý các sự cố máy móc, và lên lịch giao tiếp giữa các máy để sử dụng hiệu quả mạng và ổ đĩa. Các lập trình viên thấy rằng hệ thống này rất dễ sử dụng: hơn mười nghìn chương trình MapReduce khác nhau đã được triển khai nội bộ tại Google trong bốn năm qua, và trung bình một trăm nghìn công việc MapReduce được thực hiện trên các cụm của Google mỗi ngày, xử lý tổng cộng hơn hai mươi petabyte dữ liệu mỗi ngày.

Chúng tôi đã huấn luyện một mạng nơ-ron tích chập sâu lớn để phân loại 1,2 triệu hình ảnh độ phân giải cao trong cuộc thi ImageNet LSVRC-2010 thành 1000 lớp khác nhau. Trên dữ liệu kiểm tra, chúng tôi đạt được tỷ lệ lỗi top-1 và top-5 lần lượt là 37,5% và 17,0%, điều này tốt hơn nhiều so với công nghệ tiên tiến trước đó. Mạng nơ-ron có 60 triệu tham số và 650.000 nơ-ron, bao gồm năm lớp tích chập, một số lớp có kèm theo lớp max-pooling, và ba lớp liên kết hoàn toàn với softmax 1000 chiều cuối cùng. Để tăng tốc quá trình huấn luyện, chúng tôi đã sử dụng nơ-ron không bão hòa và một triển khai GPU rất hiệu quả của phép toán tích chập. Để giảm thiểu hiện tượng quá khớp trong các lớp liên kết hoàn toàn, chúng tôi đã áp dụng một phương pháp điều hòa được phát triển gần đây gọi là "dropout" và đã chứng tỏ rất hiệu quả. Chúng tôi cũng đã tham gia một biến thể của mô hình này trong cuộc thi ILSVRC-2012 và đạt được tỷ lệ lỗi kiểm tra top-5 chiến thắng là 15,3%, so với 26,2% đạt được bởi bài dự thi đứng thứ hai.

Privacy Integrated Queries (PINQ) is an extensible data analysis platform designed to provide unconditional privacy guarantees for the records of the underlying data sets. PINQ provides analysts with access to records through an SQL-like declarative language (LINQ) amidst otherwise arbitrary C# code. At the same time, the design of PINQ's analysis language and its careful implementation provide formal guarantees of differential privacy for any and all uses of the platform. PINQ's guarantees require no trust placed in the expertise or diligence of the analysts, broadening the scope for design and deployment of privacy-preserving data analyses, especially by privacy nonexperts.