6
Tôi cố gắng để sử dụng thuật toán Breadth-First để lấy toàn bộ cụm các kết nối mà người dùng được lựa chọn thuộc về các cách sau:Phân tích đồ thị lớn - Lấy Clusters và Tính Paths Strongest
CREATE PROCEDURE Breadth_First (@StartNode varchar(50), @LinkStrength decimal(10,7) = 0.1, @EndNode varchar(50) = NULL)
AS
BEGIN
-- Automatically rollback the transaction if something goes wrong.
SET XACT_ABORT ON
BEGIN TRAN
-- Increase performance and do not intefere with the results.
SET NOCOUNT ON;
-- Create a temporary table for storing the discovered nodes as the algorithm runs
CREATE TABLE #Discovered
(
DiscoveredUser varchar(50) NOT NULL, -- The Node Id
Predecessor varchar(50) NULL, -- The node we came from to get to this node.
LinkStrength decimal(10,7) NULL, -- positive - from predecessor to DiscoveredUser, negative - from DiscoveredUser to predecessor
OrderDiscovered int -- The order in which the nodes were discovered.
)
-- Initially, only the start node is discovered.
INSERT INTO #Discovered (DiscoveredUser, Predecessor, LinkStrength, OrderDiscovered)
VALUES (@StartNode, NULL, NULL, 0)
-- Add all nodes that we can get to from the current set of nodes,
-- that are not already discovered. Run until no more nodes are discovered.
WHILE @@ROWCOUNT > 0
BEGIN
-- If we have found the node we were looking for, abort now.
IF @EndNode IS NOT NULL
IF EXISTS (SELECT TOP 1 1 FROM #Discovered WHERE DiscoveredUser = @EndNode)
BREAK
-- We need to group by ToNode and select one FromNode since multiple
-- edges could lead us to new same node, and we only want to insert it once.
INSERT INTO #Discovered (DiscoveredUser, Predecessor, LinkStrength, OrderDiscovered)
(SELECT mc.called_party, mc.calling_party, mc.link_strength, d.OrderDiscovered + 1
FROM #Discovered d JOIN monthly_connections mc ON d. DiscoveredUser = mc.calling_party
WHERE mc.called_party NOT IN (SELECT DiscoveredUser From #Discovered) AND mc.link_strength > @LinkStrength
UNION
SELECT mc.calling_party, mc.called_party, mc.link_strength * (-1), d.OrderDiscovered + 1
FROM #Discovered d JOIN monthly_connections mc ON d. DiscoveredUser = mc.called_party
WHERE mc.calling_party NOT IN (SELECT DiscoveredUser FROM #Discovered) AND mc.link_strength > @LinkStrength
)
END;
-- Select the results. We use a recursive common table expression to
-- get the full path from the start node to the current node.
WITH BacktraceCTE(Predecessor, DiscoveredUser, LinkStrength, OrderDiscovered, Path)
AS
(
-- Anchor/base member of the recursion, this selects the start node.
SELECT d.Predecessor, n. DiscoveredUser, d.LinkStrength, d.OrderDiscovered,
CAST(n. DiscoveredUser AS varchar(MAX))
FROM #Discovered d JOIN users n ON d. DiscoveredUser = n. DiscoveredUser
WHERE d. DiscoveredUser = @StartNode
UNION ALL
-- Recursive member, select all the nodes which have the previous
-- one as their predecessor. Concat the paths together.
SELECT d.Predecessor, n. DiscoveredUser, d.LinkStrength, d.OrderDiscovered,
CAST(cte.Path + ',' + CAST(n. DiscoveredUser as varchar(30)) as varchar(MAX))
FROM #Discovered d JOIN BacktraceCTE cte ON d.Predecessor = cte. DiscoveredUser
JOIN users n ON d. DiscoveredUser = n. DiscoveredUser
)
SELECT Predecessor, DiscoveredUser, LinkStrength, OrderDiscovered, Path FROM BacktraceCTE
WHERE DiscoveredUser = @EndNode OR @EndNode IS NULL -- This kind of where clause can potentially produce
ORDER BY OrderDiscovered -- a bad execution plan, but I use it for simplicity here.
DROP TABLE #Discovered
COMMIT TRAN
RETURN 0
END
Sơ đồ (mạng xã hội) mà tôi hiện đang phân tích có 28M kết nối và không bỏ qua kết nối yếu (thiết lập treshold với @LinkStrength) thực hiện đang chạy rất dài thời gian (cho đến nay tôi đã không có bất kỳ kết quả và sẽ cố gắng để nó chạy qua đêm).
Dù sao bước tiếp theo là tính các liên kết ngắn nhất (mạnh nhất) giữa hai người dùng (có khoảng 3 người dùng). Tôi đã suy nghĩ về việc sử dụng thuật toán Djikstra nhưng không chắc liệu có thể phân tích mạng trên PC mà tôi hiện đang sử dụng (CPU Quad 2.66 GHz, RAM 4GB) và dữ liệu được lưu trữ trong cơ sở dữ liệu MS SQL Server 2008 hay không.
Để tóm tắt tôi sẽ đánh giá cao để có được một số câu trả lời/gợi ý cho các câu hỏi sau:
- Có thể thực hiện truy vấn phức tạp như một ở trên cho mô tả đồ thị (kết nối 28m, 3M người dùng) trên máy được mô tả (2,66 GHz, RAM 4GB)?
- Nếu không thể có các cách tiếp cận khác có thể theo đó thời gian thực hiện có thể bị giảm (ví dụ: tạo bảng có kết quả một phần)?
- Bạn có đề xuất bất kỳ thuật toán khác cho phát hiện cụm và tính toán đường đi ngắn nhất cho biểu đồ được mô tả không?
Cảm ơn bạn!
Nếu bạn có thể nghĩ đến một số chẩn đoán tốt mà theo đó để đoán mà tại đó các liên kết có nhiều khả năng hơn những người khác sau đó bạn có thể muốn thử A * ... – fmark
Bạn đang gần như chắc chắn I/O hơn CPU hoặc bộ nhớ bị ràng buộc, thêm cọc và phân phối các tập tin tạm thời và dữ liệu của bạn sẽ cải thiện hiệu suất SQL. Ngay cả với tối ưu hóa, về cơ bản bạn đang thực hiện một nhiệm vụ mà SQL thấy khó để tối ưu hóa, và chắc chắn sẽ tiếp tục nhấn nút cổ chai I/O khi tập dữ liệu của bạn phát triển. Hầu hết các phạm vi tiếp cận dân gian nhạy cảm với thời gian để giảm bản đồ tại thời điểm này. – stephbu