Mở đầu .1 Lý do chọn đề tài.2 Nhiệm vụ nghiên cứu của đề tài.3 Ý nghĩa khoa học của đề tài .4 Phương pháp và đối tượng nghiên cứu .5 Giới hạn và phạm vi đề tài.6 Kết quả cần đạt được. 12 2 Mô tả cụ thể bài toán: .1 Vai trò và vị trí của hệ thống trong hệ thống tổng thể.5 Hiệu suất mong muốn. 17 3 Xây dựng giải pháp.1 Giải pháp dựa trên các hệ thống database hiện có.1 Cơ sở dữ liệu quan hệ - MySql .2 Cơ sở dữ liệu theo mô hình No-SQL .3 Một số kiểm tra định lượng trên các db có sẵn .4 Đánh giá chung .2 Các kĩ thuật và công trình nghiên cứu liên quan.1 Các kĩ thuật index địa lý .2 Một số kĩ thuật cân bằng tải .3 Kĩ thuật index dữ liệu đa thuộc tính .3 Đề xuất giải pháp .1 Kiến trúc hệ thống. 49 Gom cụm dữ liệu .2 Lựa chọn Persistent Engine.
54 Mô hình dữ liệu. 55 Mô hình dữ liệu của Cassandra và dữ liệu dòng thời gian .3 Lựa chọn kĩ thuật index. 57 Tại sao chọn kd-tree thay vì r-tree? .4 Lựa chọn kĩ thuật cache. 63 4 Đo đạc và đánh giá .1 Tổ chức dữ liệu với MySQL và Mongodb .2 Đo đạc thời gian thực thi của lệnh Get(TS,TE, R(LatMin, LatMax, LonMin, LonMax)).1 Ảnh hưởng của diện tích vùng bao đến tốc độ thực thi.2 Ảnh hưởng của độ dài khung thời gian đến hiệu suất thực thi .3 Đo hiệu suất của lệnh truy vấn theo key dữ liệu, Get(TS,TE, K) .4 Đo hiệu suất của lệnh truy vấn theo key dữ liệu, có giới hạn vùng bao: Get(TS,TE, R(LatMin, LatMax, LonMin, LonMax), K).
76 8 5 Kết luận và đề xuất .1 Lý do chọn đề tài. Trong thời gian gần đây, số lượng các thiết bị có tính năng GPS được sử dụng ngày càng lớn. Dữ liệu GPS sản sinh ra từ các thiết bị này có thể được rút trích và chuyển đổi thành dữ liệu giao thông, và được sử dụng cho các giải pháp về giao thông, chẳng hạn như biểu diễn hiện trạng giao thông tại một thời điểm nào đó, dự báo giao thông, cảnh báo hiện trạng giao thông, v. Vấn đặt ra là với số lượng lớn các thiết bị tham gia vào hệ thống, một khối lượng dữ liệu sẽ được chuyển về hệ thống trong thời gian thực để lưu trữ.
Đồng thời, hệ thống cũng phải cung cấp dữ liệu một cách tức thời đến các ứng dụng liên quan. Các hệ quản trị cơ sở dữ liệu truyền thống dựa trên SQL thường chậm và không đáp ứng được yêu cầu này. Nhiệm vụ của luận văn là tìm ra một giải pháp hiệu quả cho việc lưu trữ và truy xuất lượng dữ liệu này một cách hiệu quả.2 Nhiệm vụ nghiên cứu của đề tài. Đưa ra một giải pháp có thể giải quyết bài toán truy xuất và lưu trữ dữ liệu dạng GPS trong thời gian thực.
Giải pháp có thể là một hệ thống có sẵn trên thị trường hoặc một hệ thống tự xây dựng. - Nếu là hệ thống có sẵn phải mô tả kĩ thuật lưu trữ trên hệ thống đó. Mô tả thủ tục cài đặt. Có số liệu đo đạc chứng minh hệ thống hệ thống có thể thỏa mãn yêu cầu của luận văn.
- Nếu là hệ thống tự xây dựng, phải có thiết kế kiến trúc, mô tả cách hiện thực hệ thống. Có các số liệu đo đạc cụ thể chứng minh hệ thống thỏa mãn yêu cầu lưu trữ như trong luận văn.3 Ý nghĩa khoa học của đề tài Hiện nay với sự phổ biến của các thiết bị định GPS cũng như các thiết bị cầm tay, lượng dữ liệu có gắn kèm thông tin địa lý sinh ra với tốc độ ngày càng lớn. Các giải pháp DBMS truyền thống tỏ ra không phù hợp với loại dữ liệu này. Một số giải pháp chuyên về dữ liệu địa lý tuy nhiên bỏ qua yếu tố thời gian, một số quan tâm đến yếu tố thời gian và địa lý lại tỏ ra quá tải khi dòng dữ liệu đưa vào hệ thống là trong thời gian thực.
Luận văn tìm kiếm một giải pháp giải quyết vấn đề lưu trữ dữ liệu địa lý và thời gian theo thời gian thực nhằm tạo ra nền tảng cho các hệ thống khác như: phân tích, dự báo… 1.4 Phƣơng pháp và đối tƣợng nghiên cứu - Khảo sát các hệ thống DBMS hiện có, tìm hiểu mô hình dữ liệu. Tìm cách đưa dữ liệu mẫu vào hệ thống và đưa ra các đo đạc để xem xét tính phù hợp của hệ thống. Nếu hệ thống tỏ ra quá chậm thì đưa ra biện pháp khắc phục, nếu giải pháp khắc phục quá phức tạp hoặc không hiệu quả thì chuyển qua khảo sát hệ thống khác. Các hệ thống được khảo sát chủ yếu là các hệ thống theo mô hình NoSQL.
- Trong trường hợp không tìm ra hệ thống không phù hợp, tìm hiểu các kĩ thuật index dữ liệu địa lý và thời gian dựa trên các bài báo khoa học. Xây dựng hệ thống mới dựa trên các lý thuyết đã tìm hiều được. - Đưa ra các tiêu chí và thực hiện kiểm tra hệ thống đã xây dựng được.5 Giới hạn và phạm vi đề tài - Dữ liệu để khảo sát giải pháp là dữ liệu lộ trình của xe buýt lưu thông tại Việt Nam trong vòng một tuần. - Máy tính để cài đặt là máy tính cá nhân, không phải server chuyên dụng.6 Kết quả cần đạt đƣợc - Có báo cáo khảo sát các hệ thống, giải pháp tương tự.
- Báo cáo về các lý thuyết, giải thuật căn bản của bài toán index dữ liệu theo không gian và bài toán index dữ liệu theo nhiều thuộc tính. - Có kết quả chạy thử với dữ liệu mẫu từ đó đưa ra tính khả thi của giải pháp khi triển khai. 12 2 Mô tả cụ thể bài toán: 2.1 Vai trò và vị trí của hệ thống trong hệ thống tổng thể. Từ giờ hệ thống cần xây dựng được gọi là GBStore (GPS Based data Store).
Hình dưới mô tả vị trí và vai trò cuả GBStore trong hệ thống tổng thể. Hệ thống khách 1 1 1 2 (Client) UDP server 4 5 3 GBStore Hình 1 Vai trò của hệ thống trong hệ thống tổng thể - UDP server tiếp nhận các tín hiệu GPS, hình ảnh và các loại dữ liệu khác và truyền vào hệ thống lưu trữ để xử lý sau này. - GBStore là hệ thống cần xây dựng. - Hệ thống khách(Client): Các ứng dụng dự đoán giao thông, hiển thị thông tin và các ứng dụng khác truy vấn thông tin từ hệ thống lưu trữ để phục vụ cho mục đích của chúng.
Các mũi tên mô tả các luồng dữ liệu: 13 1) Các tín hiệu GPS và các dữ liệu khác từ các phương tiện giao thông, các thiết bị có tích hợp định vị GPS hoặc các loại cảm biến khác truyền thẳng vào hệ thống tiếp nhận. 2) Hệ thống tiếp nhận này có thể forward thẳng thông tin nhận được cho các hệ thống khách để xử lý ngay trong thời gian thực. 3) Hệ thống tiếp nhận đưa các tín hiệu chứa dữ liệu nhận được vào GBStore để lưu trữ phục vụ cho tổng hợp, phân tích sau này. 4) Luồng dữ liệu đáp ứng các truy vấn từ hệ thống khách.
5) Luồng dữ liệu từ hệ thống khách đưa vào GBStore. Các dữ liệu này có thể là dữ liệu tạm sinh ra trong quá trình xử lý như tốc độ trung bình , mật độ giao thông theo từng khu vực.2 Dữ liệu Một đối tượng dữ liệu lưu trữ trong hệ thống phải có các thông tin sau đây: key: khóa do người dùng định nghĩa, time: thời gian của dữ liệu, latitude và longtitude: tọa độ địa lý của dữ liệu, dữ liệu (dạng chuỗi byte thô, hệ thống không quan tâm đến nội dung chuỗi byte này), type: kiểu dữ liệu (để phân loại dữ liệu, tương tự phân loại dữ liệu thành các bảng trong các CSDL quan hệ). Ngoài kiểu dữ liệu có gắn kèm thời gian, còn có kiểu dữ liệu không phụ thuộc thời gian. Với kiểu dữ liệu này, ta xem như một trường hợp đặc biệt của kiểu dữ liệu phụ thuộc thời gian.
Mọi đơn vị dữ liệu thuộc kiểu độc lập thời gian sẽ được gắn một trị thời gian đặc biệt nào đó để phân biệt với các đơn vị dữ liệu phụ thuộc thời gian. 14 Một đối tượng dữ liệu D (Data) được kí hiệu bằng một bộ D(T, Lat,Long, K, B) với T là thời gian, Lat và Long hợp thành tọa độ địa lý, K là khóa của dữ liệu, B là dữ liệu thô được gắn với đối tượng này. Với dữ liệu không phụ thuộc thời gian, T nhận giá trị đặc biệt kí hiệu là t0. Do thời gian thực hiện luận văn có giới hạn, do đó, để đơn giản bài toán, giả thiết mọi đơn vị dữ liệu đưa vào hệ thống đủ nhỏ và mọi đơn vị dữ liệu đều có kích thước bằng nhau để một thao tác đưa dữ liệu vào hệ thống có thể thực hiện trong một lệnh, không phải chia nhỏ dữ liệu ra nhiều phần.3 Lƣu trữ Hệ thống phải có khả năng đáp ứng dòng dữ liệu đầu vào liên tục, do đó yêu cầu lưu trữ là phải đảm bảo đáp ứng tốc độ dòng dữ liệu đầu vào lớn, tức là thời gian lưu trữ một đơn vị dữ liệu phải đủ nhỏ, nếu tốt hơn nên có khả năng lưu trữ đồng thời nhiều đơn vị dữ liệu cùng lúc trong trường hợp hệ thống có nhiều luồng dữ liệu vào.
Hệ thống phải có khả năng hoạt động tốt với dòng dữ liệu đầu vào có mật độ phân bố không đều cả về không gian lẫn thời gian (dữ liệu mẫu có phân bố không đều theo cả không gian và thời gian). Dữ liệu lưu trong hệ thống được đưa vào liên lục do đó hệ thống phải có khả năng sao lưu các dữ liệu cũ để tránh quá tải. Một thao tác đưa dữ liệu D vào hệ thống kí hiệu là Put(D). Tạm thời luận văn không xét đến thao tác xóa dữ liệu khỏi hệ thống.4 Truy vấn Hệ thống phải có thời gian đáp ứng (latency) nhanh với các yêu cầu truy xuất dữ liệu (thời gian từ lúc nhận yêu cầu đến lúc trả về kết quả).
Latency này cũng không được tăng khi có nhiều dữ liệu trong hệ thống. 15 Các điều kiện trong truy xuất: - Điều kiện về thời gian: dữ liệu trả về trong trong khoảng thời gian [t1, t2]. - Điều kiện về khóa: dữ liệu trả về có khóa bằng một số xác định. - Điều kiện về địa lý: Có 2 kiểu điều kiện địa lý: o Được bao bởi một hình chữ nhật xác định.
o Được bao bởi một hình tròn có bán kính và tâm xác định.
